[오토마타] 2. 유한 비결정적 오토마타(NFA, Non-deterministic Finite Automata)

NFA

DFA의 전이함수 δ는 가능한 모든 상태와 알파벳에 대하여, 하나의 다음 상태를 반환한다고 했다. 이 특징은 DFA의 이름에 들어간 "Deterministic(결정적인)" 이라는 수식어에서도 알 수 있다. 반면 "Non"-deterministic한 유한 오토마타인 NFA(Nondeterministic Finite Automata)의 전이함수 δ는 반환값이 하나가 아닌 여러개이거나, 0개일수도 있다.

Figure 1. NFA diagram, 출처 [1]

위 diagram의, $q_0$에서 뻗어나오는 화살표를 보자. 0이라는 입력에 대해 두 개의 화살표로 뻗어나오고 있다. 반면 $q_1$의 경우, 0이라는 입력에 대해 어떤 뻗어나오는 화살표도 찾아볼 수 없다. 위 오토마타에 "00101"이라는 입력이 들어왔을 때를 생각해보자. 이제는 상태변화가 한 줄기가 아니라, 여러 가지로 갈라지는 트리의 모습으로 나타난다. 더 이상 뻗어나갈 수 없는 stuck 상태도 확인하자. 그리고, "00101"로부터 도달한 상태들 중 하나가 최종 상태(final state)인 $q_2$이므로, 이 오토마타는 "00101"을 수용한다.

Figure 2. computation history of NFA is tree

NFA는 때로는 ε를 입력으로 허용하기도 한다. Figure 3의 오토마타는 $q_1$에서 $q_3$로 전이할 때, ε을 허용한다. 입력이 'b'라면, $q_1 \to q_2$도 당연히 가능하지만, $q_1 \to q_3 \to \text{(stuck)}$의 computation history도 가능하다.

 

나중을 위해, ε-closure의 개념을 소개한다. 어떤 상태 q로부터 ε 전이만을 이용해서 도달가능한 상태들의 집합을 의미한다. 예를 들어, Figure 3에서 $q_1$의 ε-closure는 $\{q_1, q_3\}$이다. 반면, $q_2$는 가능한 ε 전이가 없어, $q_2$의 ε-closure는 자기 자신 뿐인 $\{q_2\}$다. 이것을 $ext(q_2)=\{q_2\}$ 로 표기하기로 한다.

 

※ [2]에서는 NFA에서 ε의 입력을 허용하지만, [1]에서는 ε의 입력을 허용하고, nondeterministic한 유한 오토마타를 ε-NFA라는 이름으로 구분하고 있다. 달리 말하면, [1]은 NFA의 ε를 허용하지 않으며, NFA를 ε-NFA의 부분집합으로 여긴다. 필자는 [2]의 흐름대로 ε-NFA와 NFA를 구분하지 않고 동일하게 다룬다.

Figure 3. NFA diagram, 출처 [2]

---

 

엄격한 정의

DFA와는 다른 것은 δ의 정의뿐이다. NFA의 전이함수 δ에는 알파벳 뿐만 아니라, ε 또한 입력이 가능하다. 그리고 출력은 Q의 부분집합들의 집합, 즉, 멱집합(power set)이다. 예를 들자면, Figure 3의 $q_2$에서 'a'에 대응하는 화살표는 두 개이므로, $\delta(q_2, a) = \{q_2, q_3\}$ 라고 표현할 수 있다. 반면 $q_1$에서는 $delta(q_1, a) = \phi%다. 그리고, 어떤 NFA N이 인식하는 언어는 아래와 같이 정의된다. Figure 2에서 $\delta(q_0, 00101)=\{q_0, q_2\}$이었고, F의 원소인 $q_2$를 포함했으니, 00101은 '수용'임을 떠올리면, 아래의 정의를 이해할 수 있다.