[Automata Theory] DFA = NFA
DFA = NFA 우선, DFA가 만들 수 있는 언어는 모두 NFA로도 만들 수 있다. 이는 정의에 의해 자명하다. 그렇다면 여기서 당연히 NFA가 만들 수 있는 언어는 모두 DFA로도 만들 수 있는지에 대한 궁금증이 생긴다. 결론부터 말하면 맞다. 이를 증명하기 전에, 앞서 보았던 NFA 하나를 DFA로 바꿔보자. 위 NFA를 $M$이라고 하면 $M=(\{q_0, q_1, q_2\}, \{0, 1\}, \Delta, q_0, \{q_2\})$이다. $\Delta$의 함숫값을 구하면 $\Delta^*(q_0, 0) = \{q_0\}$ $\Delta^*(q_0, 1) = E(\Delta(q_0, 1)) = \{q_0, q_1, q_2\}$ $\Delta^*(q_1, 0) = \Delta^*(q_1, 1) ..
[Automata Theory] Language
언어(Language)라는 개념은 우리에게도 굉장히 친숙한 개념이다. 늘 사용하는 것이 언어이고 이 글도 언어의 한 종류인 한국어와 영어로 쓰여진 무언가 이다. 그렇다면 언어의 정의는 무엇일까? 우선, 언어를 정의하기 위해서는 '알파벳'과 '스트링'이라는 것이 필요하기에 이들을 먼저 알아보자. 1. 알파벳 $\Sigma$는 문자들의 Finite Set이다. 예를 들어, 영어의 경우 $\Sigma=\{a, b,\cdots,z\}$이고, 이진수의 경우 $\Sigma=\{0,1\}$이다. 2. 스트링은 알파벳 $\Sigma$에 속해있는 문자들의 유한한 나열이다. 예를 들어, "abcd"는 $\Sigma=\{a, b,\cdots,z\}$상의 스트링이다. 3. $\Sigma$상의 모든 스트링의 집합은 $\Sigm..
