이 글은 정규언어의 다양한 성질들에 대해 배운다. 첫째로, 다룰 것은 정규 언어라면 항상 성립하는 pumping lemma이다. 이 것을 통해, 우리는 어떤 언어가 정규언어인지 아닌지 쉽게 증명할 수 있다. 둘째는, 정규 언어의 닫힘성(closure)이다. 앞서, union, concatenation, Kleene star의 닫힘성을 보였듯이, 더 많은 연산자에 대한 닫힘성을 살펴본다. 셋째로, 두 오토마타의 동등성을 비교하는 방법에 대해 알아본다.Pumping Lemma어떤 정규언어 A에 대해, 항상 상수 p(pumping length라고 부름)가 존재하여:- 길이가 p 이상인 A의 모든 문자열 w는- w를 $w=xyz$ 세 부분으로 나눌 수 있고,- 다음 조건을 만족한다.1. $|y| \ge 1 $2..

우리는 지금까지 특정 기능만 수행하는 튜링머신을 다뤘다. 이것을 고정 튜링머신(Hardwired TM)이라고 부른다. 어떤 1번 TM이 w에 대해서 수행하는 일도, 2번 TM이 y에 대해 수행하는 일도, 3번 TM이 z에 대해 수행하는 일도 다 해내는 범용 튜링머신(Universal TM)에 대해 알아본다. 범용 튜링머신(Universal TM)만약 어떤 튜링머신 M에 대한 정보와 M이 원래 입력으로 받는 문자열 w를 함께 입력으로 받아서 동작하는 프로그래머 TM(programmable TM)이 있다면, 그것이 곧 범용 튜링머신(UTM)이 될 것이다. UTM은 M이 하는일을 흉내내서 w에 대한 연산을 처리한다. 이 UTM의 동작 방식은 쿠르트 괴델(Kurt Friedrich Gödel)에 의해 제시되었다..

이번 글에서는 튜링머신에 변형을 가해서, 새로운 튜링머신을 만든다. 새로운 튜링머신들은 기존 튜링머신보다 좋아보이지만, 우리의 직관과 추론에 도움을 줄 뿐, 기존 튜링머신과 같은 언어를 인식한다. 달리 말하면, 동등하다.헤드를 움직이지 않아도 되는 튜링머신앞선 튜링머신은 매 전이마다 헤드를 왼쪽이나 오른쪽으로 움직여야했다. 하지만, 변형된 튜링머신은 헤드를 가만히 있어도 된다. 원래 튜링머신의 전이 함수는 $Q\times\Gamma \to Q\times\Gamma\times\{L, R\}$ 이었다면, $Q\times\Gamma \to Q\times\Gamma\times\{L, R, S\}$의 함수다.왜 $S$를 추가하고도 기존 튜링머신과 동등할까? $\delta(q, a) = (q',b,S)$를 기존 튜..

튜링머신은 DFA, PDA와는 다른 또 새로운 오토마타다. 1. 읽기-쓰기 테이프(Read-write tape)를 갖는다. 테이프는 오른쪽으로 무한하다. 테이프의 초깃값은 입력 문자열로 채워져 있으며, 나머지는 blank(⊔)로 채워져있다.2. 최초에 헤드(Head)는 가장 왼쪽 셀(cell)을 가리키고 있다.3. 이제 오토마타는 매 전이마다 아래의 행동을 해야한다.→ 헤드를 오른쪽 혹은 왼쪽으로 움직인다.→ 심볼(symbol)의 값을 다른 심볼로 바꾸거나 그대로 둔다.→ 상태를 옮긴다. 튜링머신(TM)의 엄격한 정의(Formal Definition)$\text{TM is a 7-tuple}(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{rej..

":)" 문제가 있다고 생각해보자. ":)" 문제는 어떤 프로그램이 :)를 출력하는지 아닌지를 확인하는 문제다. 결론부터 말하자면, 컴퓨터는 이 단순한 문제를 항상 해결하지 못한다. 만약 이런 프로그램이 입력으로 들어온다면 문제의 정답을 "yes"라는걸 쉽게 알 수 있다.int main() { printf(":)");}하지만, 이런 문제라면 어떨까? 코드의 내용을 간단히 요약하자면, n을 입력받고, 가능한 모든 정수쌍 (x,y,z)를 순회하면서 $x^n+y^n=z^n$가 성립하면 ":)"를 출력하는 코드다. 가령 $n=2$라면, $3^2+4^2=5^2$에서 ":)"가 출력될 가능성이 있다.int main() { int n, tot, x, y; scanf("%d", &n); while(1) { ..

기본 정규 연산우리는 지금까지, 결정적/비결정적 유한 오토마타의 정의를 배웠다. 앞으로는 오토마타와 정규언어들의 속성들에 대해 다룰 것이다. 그 이전에, 이 속성들을 익히거나 증명하는데에 유용한 도구상자들을 준비했다. 아래의 3가지 연산은 정규 연산(regular operation)이라 불리는 기본적인 언어들 간의 연산이다. 어떤 언어 A,B에 대하여 아래처럼 정의된다. Kleene는 클레이니, 클리네 등으로 발음하는 듯 하다. 우리는 자연수 $\times$ 자연수가 자연수라는 사실을 알고 있다. 이것을 수학에서는 자연수가 곱셈에 대하여 닫혀있다(closed)고 말한다. 마찬가지로, 정규언어는 위 3가지 기본 정규 연산에 대하여 닫혀있다. 예를 들어, 정규언어와 정규언어의 union은 정규언어다. 달리 ..

카이스트 CS322 형식언어 및 오토마타 공부 내용입니다.정규언어1. 유한 결정적 오토마타(DFA, Deterministic Finite Automata)2. 유한 비결정적 오토마타(NFA, Non-deterministic Finite Automata)3. DFA와 NFA의 동등성4. 정규표현식과 NFA의 동등성5. Pumping Lemma6. 정규언어의 폐쇄성(Closure)과 동등성7. 정규언어의 최소화8. 마이힐-네로드 정리(Myhill-Nerode Theorem)9. Monadic Second-Order Logic(MSO) 문맥 자유 언어10. 문맥 자유 언어(Context Free Language) 11. 푸쉬다운 오토마타(PDA, Pushdown Automata)12. PDA와 CFG의 동등성..

정규표현식우리는 언어를 "1로 시작하는 문자열" 혹은 "1이 짝수번 들어가는 문자열" 등으로 주절주절 표현했다. 좀 더 편리하고, 수학적으로 표현하는 방법은 없을까? 앞서 배운 3가지 기본 연산, union, concatenation, Kleene star을 이용해서 표현할 수 있다. 어떤 정규표현식 R이 표현하는 언어는 $\mathcal{L}(R)$ 이라고 표기하고, 정규표현식 R의 언어(language of R)라고 부른다.{1이 딱 한 번 들어가는 문자열} = $\mathcal{L}(0^*10^*)${최소 1이 한 번 들어가는 문자열} = $\mathcal{L}(\{0,1\}^*1\{0,1\}^*)${짝수 길이의 문자열} = $\mathcal{L}((\Sigma\Sigma)^*)$ 이게 정규표현식이..