[Automata Theory] Nondeterministic Finite Automata

What is Nondeterministic Finite Automata?

비결정 유한 오토마타(Nondeterministic Finite Automata, 일명 NFA)는 DFA의 확장 버전이다. 결정과 비결정이 말하는 것은 상태인데, DFA는 특정 상태에서 특정 알파벳을 읽었을 때 다음 상태가 '결정'되는 반면, NFA는 다음 상태가 하나 이상일 수도 있고, 알파벳을 읽지 않고도 상태가 전이될 수 있다 ($\epsilon$에 의한 전이). 이제 NFA 역시 엄밀하게 정의해보자.

Definition

NFA $M$은 5가지의 구성 요소가 있어 $\boldsymbol{M=(Q, \Sigma, \Delta, q_0, F)}$이다. 이때 각 요소들은

 

1. $Q$ : 상태 집합 (유한집합)
2. $\Sigma$ : 알파벳
3. $\Delta: Q\times (\Sigma\cup\{\epsilon\})\rightarrow \mathcal{P}(Q)$ : 전이 함수 ($\mathcal{P}(Q)$는 $Q$의 Power set)
4. $q_0 \in Q$ : 초기 상태
5. $F\subseteq Q$ : 최종 상태의 집합

이다.

 

DFA와 비교했을 때 달라진 것은 전이 함수뿐이다. 설명의 편의를 위해 $\Delta$를 조금 확장한 함수 $\Delta^*: Q\times (\Sigma^*\cup\{\epsilon\})\rightarrow \mathcal{P}(Q)$를 정의해보자.

 

1. $E(q) :=$ $q$에서 시작하여 $\epsilon$만을 통해 전이할 수 있는 상태 ($q$도 포함)
2. $\Delta^*(q, \epsilon) := \Delta(q, \epsilon)$
3. $w\in \Sigma^*, a\in \Sigma$에 대해 $\Delta^*(q, wa) := E(\Delta(\Delta^*(q, w), a))$

NFA 역시 언어를 표현하는 방식인데, NFA $M$이 받아들이는 스트링의 집합을 $L(M)$은 아래와 같다.

 

$L(M)=\{w\in \Sigma^* : \Delta^*(q_0, w)\cap F \neq \phi\}$

 

즉, 입력을 모두 받았을 때 NFA가 가지는 상태들 중에 $F$에 속하는 것이 하나라도 있으면 입력된 스트링은 받아들이는 것이다.

Example

$\{0, 1\}^*$에 속하는 스트링 중 끝자리가 1이거나 끝에서 두 번째 자리가 1인 스트링을 받아들이는 NFA를 만들면 아래와 같을 것이다.

생각보다 정말 간단하지 않은가? 이를 DFA로 표현하려 했으면 더 많은 상태들이 필요했을 것이다. 또한, NFA를 생각하는 과정도 매우 간단한데, 끝에서 세 번째나 두 번째 알파벳까지는 $q_0$에서 머물다가 끝에서 두 번째나 마지막 알파벳은 1이어야 하므로 1을 읽어 $q_1$으로 전이한다. 그리고 방금 전 읽은 알파벳이 끝에서 두 번째였다면 $0, 1$을 통해, 끝자리였다면 $\epsilon$을 통해 $q_2$로 전이하게 되고 $q_2$는 최종 상태에 포함되어 있으므로 이 스트링을 받아들이게 된다. 물론 이는 단지 사고 과정일 뿐 실제로 이 NFA가 이렇게 동작한다는 것은 아니다 (실제로는 여러 상태를 가지는데 이렇게 보이는 것이다).

Note

눈치가 빠른 사람이라면 눈치챘겠지만 Example에 있는 NFA는 무언가 불완전하다. 자세히 살펴보면 $q_0$에서 $\epsilon$에 의한 전이를 할 경우와 $q_2$에서 알파벳을 더 읽을 경우 어떤 상태로 전이할지 명시되어있지 않다. 이는 $\phi\in\mathcal{P}(Q)$(공집합)으로의 전이를 의미한다. 즉, $q_2$에서 알파벳을 더 읽을 경우 아무 데도 있지 못하게 된다.

 

반면, DFA를 그린 그림에서도 이렇게 불완전한 것이 있는데, 이는 그림을 보다 단순하게 그리는 기법으로 $q_2$에서 0 또는 1을 읽게 될 경우 Dead State로 전이한다는 것을 뜻한다. 여기서 Dead State(죽은 상태)는 한번 들어가면 빠져나올 수 없는 상태를 의미하며 최종 상태 역시 아니다. 따라서 크게 의미가 있는 상태는 아니며 명시되어 있지 않은 전이 함수의 결과는 모두 이 Dead State라고 생각하면 된다. 때로는 이런 부연 설명을 생략하기 위해 DFA의 전이 함수를 해당 정의역의 부분 정의 함수(partially defined function)로 정의하기도 한다. 어떤 방식으로 생각하든 차이는 없고 NFA와도 마찬가지로 최종 상태는 절대 될 수 없는 어딘가로 간다고 생각하면 편하다. (수정: 22.10.12)

 

NFA가 가지는 흥미로운 사실이 하나 더 있는데, 이는 바로 항상 최종 상태가 하나만 있다고 가정할 수 있다는 것이다. 증명은 생각보다 단순한데, 만약 최종 상태가 여러 개 있다면 새로운 상태를 하나 정의하고 기존의 최종 상태들에서 새로운 상태로 $\epsilon$에 의한 전이가 가능하도록 만든 뒤 새로운 상태를 새로운 최종 상태로 정의하면 이 역시 NFA가 되며 최종 상태가 하나가 된다.

 

 

 

* 이 글은 서울대학교 박근수 교수님의 '오토마타이론' 강의자료에 기반을 두고 있고, 교수님의 허락을 받고 포스팅을 진행함을 밝힌다.