이번엔 \(\varepsilon\)-전이가 없는 NFA를 DFA로 변환해보자. 변환 알고리즘은 다음과 같다. NFA에 의해 인식되는 언어를 L이라고 하면 L을 인식하는 DFA가 존재한다. L을 인식하는 NFA \(M = (Q, \sum , \delta , q_0, F\)라 하면 L을 인식하는 DFA \(M^\prime = (Q^\prime, \sum , \delta^\prime, q_0^\prime, F^\prime\)는 다음과 같이 구성된다. \(Q^\prime = 2^Q\), 즉 \(Q^\prime\)의 한 상태는 \([q_1, q_2, \cdots , q_i]\)의 형태로 나타낸다. 단, \(q_j \in Q(j=1, 2, \cdots , i\)이다. \(F^\prime=\{q \in Q^\prim..

NFA에서 DFA로 변환하기 전에 NFA와 DFA가 서로 동등해야만 변환의 의미가 있다. 다만 증명 부분은 생략한다. NFA와 DFA는 동등하다는 것만 알고 넘어가자. \(\varepsilon\)-전이가 있는 NFA를 DFA로 변환 \(\varepsilon\)-closure를 이용하여 변환하는데 NFA에서 의미가 같은 여러 개의 상태가 DFA에서 하나의 상태로 변환되는 것이다. 먼저 \(\varepsilon\)-closure(S)에 대한 정의부터 살펴보자. \(\varepsilon\)-closure(S) S가 하나의 상태일 경우 \(\varepsilon\)-closure(S)는 NFA의 상태 S와 상태 S로부터 \(\varepsilon\)-전이에 의해 도달될 수 있는 NFA의 모든 상태의 결합이다. 이 ..