비결정론적 유한 상태 기계

(0|1)^* 1 (0|1)³을 인지하는 NFA.
같은 언어를 인지하는 DFA는 적어도 16개의 상태가 필요하다.

오토마타 이론에서, 어떤 유한 상태 기계가 결정론적 유한 상태 기계(DFA)라는 것은 다음을 뜻한다.

• 현재 상태와 입력에 따라 다음 상태가 유일하게 결정된다.
• 상태가 바뀌려면 입력이 필요하다.

비결정론적 유한 상태 기계(Nondeterministic finite automaton, NFA)는 이러한 제한을 따르지 않을 수도 있다. 모든 DFA는 NFA이기도 하다. NFA는 좁은 뜻으로는 DFA가 아닌 유한 상태 기계만을 가리키기도 하지만, 이 문서에서는 그렇게 하지 않는다.

멱집합 구성을 사용하면 주어진 NFA와 동등한 DFA를 만들 수 있다. 즉, 주어진 NFA와 같은 언어를 인지하는 DFA를 만들 수 있다. DFA와 마찬가지로 NFA가 인지할 수 있는 언어는 정규 언어뿐이다.

미하엘 라빈과 데이나 스콧은 1959년에 비결정론적 유한 상태 기계를 처음 도입했고 NFA와 DFA가 동등함을 보였다. NFA는 정규 표현식의 구현에 사용된다. 톰슨 구성은 정규 표현식을 NFA로 바꾸어 효율적인 문자열 패턴 매칭을 가능케 하는 알고리즘이다. 반대로 클레이니 알고리즘은 NFA를 정규 표현식으로 바꾸어 준다. (이때 정규 표현식의 길이는 NFA의 크기에 따라 지수적으로 증가한다.)

NFA를 더 일반화한 개념으로 ε-이동을 허용하는 NFA, 유한 상태 트랜스듀서, 푸시다운 오토마타, 교대 유한 상태 기계, ω-오토마타, 확률적 오토마타 등이 있다. NFA의 특수한 예로는 DFA 말고도 비중의적 유한 상태 기계(UFA)와 자기 검증 유한 상태 기계(SVFA) 등이 있다.

개요

비결정론적 유한 상태 기계를 직관적으로 설명하는 방법은 여러 가지가 있다.

• NFA는 DFA처럼 입력 문자열을 받아들인다. 입력 기호 하나를 읽을 때마다 상태가 바뀌고, 모든 입력 기호를 읽을 때까지 계속 동작한다. 매 단계마다 NFA는 가능한 다음 상태 중 하나를 임의로 선택한다. 모든 기호를 읽은 뒤에 “운 좋게” 최종 상태 중 하나에 도착할 수 있다면, 입력을 수용한다. 그런 방법이 없다면 입력을 수용하지 않는다.^:19:319
• NFA는 입력 기호를 하나씩 받아들인다. 매 단계마다, 가능한 다음 상태가 하나보다 많다면, NFA는 스스로를 필요한 만큼 “복제”하고 각 복사본은 서로 다른 가능한 상태로 진입한다. 가능한 다음 상태가 없다면, 그 복사본은 막다른 길에 다다랐으므로 “죽는다”. 모든 기호를 읽은 뒤에 복사본 중 하나라도 최종 상태에 도착했다면, 입력을 수용한다. 최종 상태에 도달한 복사본이 없다면 입력을 수용하지 않는다.^{:19–20:48:56}

정의

기계

비결정론적 유한 상태 기계는 순서 5짝 $(Q,\Sigma ,\Delta ,q_{0},F)$으로 정의된다. 각 요소의 의미는 다음과 같다.

• 가능한 상태의 유한집합 $Q$.
• 입력 기호의 유한집합 $\Sigma$.
• 전이 함수 $\Delta$ : $Q\times \Sigma \rightarrow P(Q)$.
• 초기 상태 $q_{0}\in Q$.
• 최종 상태 (또는 수용 상태)의 집합 $F\subseteq Q$.

이때 $P(Q)$는 $Q$의 멱집합을 나타낸다.

언어

NFA $M=(Q,\Sigma ,\Delta ,q_{0},F)$이 인지하는 언어를 $L(M)$이라 쓰고, $M$이 수용하는 $\Sigma$ 위의 모든 문자열의 집합으로 정의한다.

$M$이 문자열 $w=a_{1}a_{2}...a_{n}$을 수용한다는 것은 여러 가지 방식으로 정의할 수 있는데, 앞서 소개한 직관적인 정의에 어느 정도 대응한다.

• $w$가 수용된다는 것은, $Q$에 속한 상태 $r_{0},r_{1},...,r_{n}$이 존재하여 다음을 만족한다는 것이다.
  1. $r_{0}=q_{0}$
  2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$, ($i=0,\ldots ,n-1$)
  3. $r_{n}\in F$.

풀어서 설명하면, 첫째 조건은 기계가 초기 상태 $q_{0}$에서 시작한다는 것이다. 둘째 조건은 문자열 $w$의 각 기호를 읽을 때마다 기계가 전이 함수 $\Delta$에 따라 한 상태에서 다른 상태로 바뀐다는 것이다. 셋째 조건은 기계가 $w$의 마지막 기호를 읽고 최종 상태 중 하나로 바뀐다면 $w$를 수용한다는 것이다. $M$이 $w$를 수용하려면 가능한 모든 상태의 수열이 최종 상태로 끝날 필요는 없다. 가능한 상태의 수열 중 하나라도 최종 상태로 끝나면 충분하다. 만약 그렇지 않다면, 즉 $q_{0}$에서 출발해서 $w$를 따라 $F$에 속한 상태로 갈 방법이 전혀 없다면 NFA가 문자열을 수용하지 않는다. $M$이 수용하는 모든 문자열의 집합을 $M$이 인지하는 언어라고 하며 $L(M)$으로 나타낸다.^:320:54

• 다른 정의로, $w$가 수용된다는 것은 $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$라는 뜻이다. 이때 $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$는 다음과 같이 재귀적으로 정의된다.
  1. $\Delta ^{*}(r,\epsilon )=\{r\}$, ($\epsilon$은 빈 문자열을 나타낸다)
  2. 모든 $x\in \Sigma ^{*},a\in \Sigma$에 대해 $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$.

폴어서 설명하면, $\Delta ^{*}(r,x)$은 상태 $r$에서 출발해서 문자열 $x$를 읽고 도달할 수 있는 모든 상태의 집합이다. $q_{0}$에서 출발해서 문자열 $w$를 따라 $F$에 속한 상태 중 하나에 도달할 수 있다면, 문자열 $w$를 수용한다.^:21:59

초기 상태

위의 정의에서는 초기 상태가 하나뿐이지만 꼭 그럴 필요는 없다. 어떤 경우에는 여러 개의 초기 상태를 갖도록 NFA를 정의하기도 한다. 이렇게 하면 표기가 편리해지는 경우가 있다. 초기 상태가 여럿인 NFA를 초기 상태가 하나인 동등한 NFA로 변환하는 것은 간단하다.

예시

M의 상태 도표. 상태 p에서 입력 1을 받으면 p 또는 q로 갈 수 있기 때문에 비결정론적이다.	입력 “10”을 받았을 때 M의 가능한 모든 작동.
입력 “1011”을 받았을 때 M의 가능한 모든 작동. 호 첨자: 입력 기호, 노드 첨자: 상태, 초록: 초기 상태, 빨강: 최종 상태.

다음 기계 $M$은 {0, 1} 위의 입력을 받아들여 입력이 1로 끝나는지 판정한다.

$M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$이라 하자. 단, 전이 함수 $\Delta$는 다음 상태 전이 표와 같이 정의한다. (왼쪽 위 그림 참조)

입력 상태	0	1
$p$	$\{p\}$	$\{p,q\}$
$q$	$\emptyset$	$\emptyset$

집합 $\Delta (p,1)$은 하나보다 많은 상태를 포함하므로, $M$은 비결정론적이다. $M$의 언어는 정규 표현식 (0|1)*1에 대응하는 정규 언어이다.

입력 “1011”을 받았을 때 $M$이 작동할 수 있는 모든 경우의 수는 아래쪽 그림에 나타나 있다. 상태의 수열 중 하나가 위 정의를 만족시키므로 $M$은 이 문자열을 수용한다. 다른 수열이 실패하는 것은 상관없다. 이 그림은 여러 가지 방식으로 읽을 수 있다.

• 첫번째 직관적 설명에 따르면, 그림에 나타난 각 경로는 $M$이 취할 수 있는 일련의 선택을 나타낸다.
• “복제”에 기반한 설명에 따르면, 각 세로줄은 어느 시점에서 $M$의 모든 복사본을 보여준다. 한 노드에서 여러 화살표가 나오는 것은 복제를 나타내고, 화살표가 나오지 않는 노드는 복사본이 “죽었음”을 나타낸다.

같은 그림을 두 가지 방식으로 읽을 수 있다는 데서 두 가지 설명이 동치임을 알 수 있다.

• 위의 첫번째 형식적 정의에 따르면, $M$은 “1011”을 읽고 상태를 $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$와 같이 바꿔 나갈 수 있기 때문에 “1011”을 수용한다.
• 두번째 형식적 정의에 따르면, $\Delta ^{*}(p,\epsilon )=\{p\}$이므로 $\Delta ^{*}(p,1)=\Delta (p,1)=\{p,q\}$이고, 따라서 $\Delta ^{*}(p,10)=\Delta (p,0)\cup \Delta (q,0)=\{p\}\cup \{\}$이므로 $\Delta ^{*}(p,101)=\Delta (p,1)=\{p,q\}$이고, 따라서 $\Delta ^{*}(p,1011)=\Delta (p,1)\cup \Delta (q,1)=\{p,q\}\cup \{\}$이다. 이 집합은 $\{q\}$와 서로소가 아니므로 “1011”은 수용된다.

반면에 $M$은 문자열 “10”을 수용하지 않는데, 마지막 기호인 0을 읽고 유일한 최종 상태인 $q$에 도달하는 것은 불가능하기 때문이다. (오른쪽 위 그림 참조) 첫 기호인 1을 읽으면 상태 $q$에 도달하게 되겠지만, 이는 “10”이 수용된다는 뜻이 아니라 “1”이 수용된다는 뜻이다.

참고 문헌

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (see section 1.2: Nondeterminism, pp. 47–63.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)