NFA를 DFA로 바꾸기

비결정적 오토마타를 결정적 오토마타로 바꾸는 방법을 알아보자. 이로써 비결정적 오토마타와 결정적 오토마타의 계산 능력이 같다는 것을 증명할 수 있다.

기본 아이디어

ε 전이가 없는 비결정적 오토마타 ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩가 있다고 하자. 다음을 만족하도록 결정적 오토마타 ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩를 만든다.

Q_D ⊆ 2^Q_N
Σ_D = Σ_N
p₀ = {q₀}
F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

전이 함수 δ_D는 다음과 같이 정의한다.

$\forall Q \in Q_{D}, a \in Σ_{D} : δ_{D} (Q, a) = ⋃_{q \in Q} δ_{N} (q, a)$

이 정의는 무슨 뜻일까? 비결정적 오토마타는 여러 상태에 동시에 있을 수 있으므로, 예를 들어 비결정적 오토마타가 상태 {q₀, q₁}에 있는 상황이 생길 수 있다. 다음 기호, 예를 들어 1을 읽으면 상태의 집합 {q₀, q₂, q₃}에 갈 수 있다. 같은 오토마타의 결정적 버전에서는 두 상태를 만들어 각각 {q₀, q₁}과 {q₀, q₂, q₃}으로 이름 붙이고, 그 사이에 기호 1에 대한 전이를 둔다. 형식적으로는 한 상태에서 다른 한 상태로 가지만, 이름 덕분에 비결정적 오토마타에서라면 각각 두 상태, 세 상태에 있었을 것임을 알 수 있다.

예

다음 비결정적 오토마타가 있다고 하자.

결정적 오토마타를 만들려면 무엇보다 새 전이 함수를 만들어야 한다. 이때 모든 전이를 적어 넣을 표를 쓰면 편하다. 처음에 표는 다음과 같다.

$\begin{array}{ccc} 상태 / 기호 & 0 & 1 \\ {q_{0}} \end{array}$

알고리즘이 끝나면 왼쪽 열에는 결정적 오토마타의 모든 상태가 들어간다. 그리고 다 채운 표가 전이 함수를 정한다. 이제 상태 {q₀}에서 입력 기호가 0과 1일 때 어느 상태로 가는지 표에 적는다.

$\begin{array}{ccc} 상태 / 기호 & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

상태 q₀에서 기호 0에 대한 전이는 상태 q₁로만 가고, 기호 1에 대한 전이는 상태 q₁과 q₂로 간다. 이제 표에 두 새 상태 {q₁}과 {q₁, q₂}를 추가한다. 왜 그럴까? 표에 상태의 집합을 적었는데 그 집합이 아직 왼쪽 열에 없으면 왼쪽 열에 그 집합을 추가하기 때문이다.

$\begin{array}{ccc} 상태 / 기호 & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} \\ {q_{1}, q_{2}} \end{array}$

그리고 다시 표를 채운다. 상태 {q₁, q₂}에서는 두 상태를 모두 확인해야 한다. 즉 상태 q₁에서 갈 수 있는 곳과 상태 q₂에서 갈 수 있는 곳의 합집합을 구한다.

새 상태가 몇 개 생겼으므로 표에 추가해야 한다.

…그리고 다시 전이를 채운다.

$\begin{array}{ccc} 상태 / 기호 & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{1}, q_{2}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{2}, q_{3}} \\ {q_{0}, q_{3}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

상태 {q₀, q₁, q₃}, {q₁}, {q₁,q₂}는 이미 있으므로 상태 {q₀,q₁,q₂,q₃}만 추가한다.

더는 새 상태를 추가하지 않았으므로 표가 완성되었다. 이제 상태 전이도만 그리면 된다. 결정적 오토마타의 상태는 첫 번째 열에 있고, 기호 0과 1에 대한 전이는 나머지 열에 있다. 원래 오토마타의 수락 상태를 포함하는 상태는 모두 이 오토마타에서도 수락 상태가 된다. 즉 q₃을 포함하는 상태는 모두 수락 상태이다. 오토마타는 다음과 같다.

이 오토마타가 실제로 올바르게 동작하는지 확인해 보자. 문자열 11001을 수락해 보자. 결정적 오토마타에서는 다음 경로를 따라간다.

$q_{0} \to^{1} q_{1}, q_{2} \to^{1} q_{0}, q_{3} \to^{0} q_{1} \to^{0} q_{0}, q_{1}, q_{3} \to^{1} q_{0}, q_{1}, q_{2}, q_{3}$

마지막 상태 {q₀, q₁, q₂, q₃}이 수락 상태이므로 오토마타는 문자열을 수락한다. 비결정적 오토마타를 시뮬레이션해도 같은 상태들을 거친다. 즉 상태 q₀에서 시작하여 기호 1로 상태 {q₁, q₂}에 간다. 다음 기호 1로 상태 {q₀,q₃}에 가고, 그다음도 마찬가지이다. 마지막에는 모든 상태 {q₀, q₁, q₂, q₃}에 있게 되고 오토마타는 문자열을 수락한다.

참고 자료

목차: 유한 오토마타, 완전 오토마타, 비결정적 유한 오토마타, 비결정적 오토마타의 시뮬레이션, NFA를 DFA로 바꾸기

« 이전: 비결정적 오토마타의 시뮬레이션

다음: 오토마타의 최소화 »