[형식언어] NFA의 DFA 변환

NFA에서 DFA로의 변환

 앞 포스팅에서는 비결정적 유한 오토마타인 NFA에 대해 알아보았다. 확실히 DFA에 비해서 NFA는 전이 가능한 상태수가 많아져 확연히 복잡하게 느껴졌을 것이다. 실제로 NFA는 언어의 구조를 쉽게 표현할 수 있지만 DFA보다 프로그램으로 구현하기 어렵다. NFA에서 스트링을 인식하는 과정은 어떤 상태에서 전이 함수를 거쳐 또 다른 상태로 전이되는 것으로 진행된다. 이때, NFA는 여러 상태로 전이 가능하므로 상태들의 집합에서 심벌을 보고 또 다른 상태 집합으로 전이된다. 여기서 상태 집합이라는 말에 주목해보자. {a, b, c}와 같은 상태 집합을 아예 X로 간주한다면, NFA도 결정적으로 전이될 수 있다. 상태들의 집합 Q가 유한 집합이기 때문에 $2^{Q}$ 역시 유한 집합이다. 이것을 종합하여, NFA를 DFA로 변환해보자.

 

NFA M = (Q, Σ, δ, q₀, F)에 의해 인식되는 언어를 L이라 하면, L을 인식하는 DFA M' = (Q', Σ', δ', q₀', F')는 다음과 같이 구성된다.

1. Q' = $2^{Q}$(Q의 부분 집합의 집합). Q의 한 상태는 [q₁, q₂, ..., q_i]의 형태로 표기.

2. q₀' = [q₀]

3. F' = {q  Q' | q는 F의 상태들 중 적어도 하나를 포함하는 상태}

4. δ({q₁, q₂, ..., q_i}, a) = {p₁, p₂, ..., p_i} 이면, δ'([q₁, q₂, ..., q_i], a) = [p₁, p₂, ..., p_i] 이다.

 

위 정리를 활용해 아래 NFA를 DFA로 바꿔보자.

NFA M = ({q₀, q₁}, {0, 1}, δ, q₀, {q₁})

δ	0	1
q0	{q0, q1}	{q0}
q1	∅	{q0, q1}

 먼저, 상태 집합 Q'는 공집합을 제외한 $2^{Q}$이므로 {[q0], [q1], [q0, q1]}이고, 시작 상태 q0'는 [q0]이다. M에서 종결 상태 q1을 포함하는 집합을 Q'에서 찾으면 F' = {[q1], [q0, q1]}이다. 마지막으로 전이 함수를 변환해보자.

δ': δ'([q0], 0) = [q0, q1],    δ'([q0], 1) = [q0],    δ'([q1], 0) = ∅,    δ'([q1], 1) = [q0, q1],     δ'([q0, q1], 0) = [q0, q1],     δ'([q0, q1], 1) = [q0, q1]. 

 

δ'	0	1
[q0]	[q0, q1]	[q0]
[q1]	∅	[q0, q1]
[q0, q1]	[q0, q1]	[q0, q1]

 변환된 상태 전이표를 이렇게 바꾸어 보았다. 그런데 지금은 상태의 수가 적어 이렇게 보아도 큰 무리는 없지만, 상태 수가 더 늘어난다면 상태 전이표를 보는 것에도 어려움이 있을 것이다. 그러니 이 상태 전이표를 아래와 같이 바꾸어보자!

δ'	0	1
A	C	A
B	∅	C
C	C	C

 상태 전이표가 훨씬 간결해졌다. 이제 이 결정적인 유한 오토마타를 다이어그램으로 그려낼 수 있다.

 

 이렇게 DFA를 다이어그램으로 그려보았고, 위 정리를 이용해 NFA를 DFA로 변환하면 이론적으로 $2^{|Q|} - 1$개라는 많은 상태 수를 가지게 된다. 그런데 여기서, 상태 B와 같이 시작 상태에서 도달할 수 없는 상태는 제거할 수 있으므로 실질적으로는  $2^{|Q|} - 1$보다는 적은 상태 수를 가지게 된다. 이것은 나중에 DFA의 상태수 최소화에서 더 자세히 알아보겠다. 

 

 여기서 NFA의 시작 상태를 DFA의 시작 상태로 놓고, 각 상태에서 입력 심벌을 보고 갈 수 있는 다음 상태들을 구한다. 여기서 구한 상태가 앞서 구한 상태라면 Q'에 추가할 필요는 없다. 반대로 새로운 상태가 등장하였다면, 이 상태를 Q'에 추가하고 입력 심벌을 보고 갈 수 있는 다음 상태들을 구한다. 이 과정을 새로운 상태가 등장하지 않을 때까지 반복하여 NFA를 도달 불가능한 상태가 없는 DFA로 변환할 수 있다.

 

ε-전이를 가지는 NFA에서 DFA로의 변환

 앞에서 살펴본 NFA는 ε-전이를 가지지 않는 유한 오토마타였다. 이제 ε-전이를 가지는 NFA를 DFA로 변환하는 방법을 알아볼 것인데, ε-전이란 ε를 보고 한 상태에서 다음 상태로 이동하는 것을 의미한다. 쉽게 말해서 ε을 보고 전이하는 경우인 아무 심볼도 보지 않고 전이하는 경우를 고려하는 것이다. ε-NFA를 DFA로 변환하기 위해서 한 상태에서 ε을 보고 갈 수 있는 상태들을 모두 구하여야 하며, 이와 같은 기능을 하는 함수를 ε-CLOSURE라 한다.

 

 CLOSURE(X)를 구하는 방법은 그리 어렵지 않다. 현재 상태 X와 ε을 보고 이동할 수 있는 모든 상태를 추가해주기만 하면 된다. 아래 ε-NFA에서 CLOSURE를 구해보자.

 클로저는 앞서 현재 상태와 ε을 보고 이동할 수 있는 모든 상태를 포함하면 된다고 하였다. 따라서 CLOSURE(A) = {A, B, D}가 된다. 마찬가지로 C의 CLOSURE인 CLOSURE(C) = {C, D}이고, CLOSURE(A, C) = {A, B, C, D}가 된다. 클로저를 구하는 방법도 알아보았으니, 이제 ε-NFA를 DFA로 바꾸어보자.

 

 위 ε-NFA에서 시작 상태는 1이 ε-전이를 포함하므로 CLOSURE(1)이 시작 상태가 된다. 따라서 CLOSURE(1)을 먼저 구하면 CLOSURE(1) = {1, 3, 4} = [1, 3, 4]가 된다. 여기서 4가 왜 클로저에 포함되는지 의문을 가질 수 있는데, 1에서 ε를 보고 3으로 전이하고, 그 상태에서 ε를 보고 4로 전이될 수 있으므로 4가 클로저에 포함된다. 이제 각 입력 심벌에 따라 이동할 수 있는 상태를 구하여 ε-CLOSURE를 취한 것이 다음 상태가 되며, 더 이상 새로운 상태가 등장하지 않을 때 까지 전이를 계속하자. 

 

δ	a	b	c
CLOSURE(1) = [1, 3, 4]	ε-CLOSURE(2) = [2]	∅	ε-CLOSURE(3) = [3, 4]
[2]	∅	[4]	∅
[3, 4]	∅	∅	ε-CLOSURE(3) = [3, 4]
[4]	∅	∅	∅

 위 상태 전이표 역시 직관적으로 이해가 어렵다. 그러니 [1, 3, 4] = A, [2] = B, [3, 4] = C, [4] = D로 치환하여 표를 다시 작성해보자. 

δ	a	b	c
A	B	∅	C
B	∅	D	∅
C	∅	∅	C
D	∅	∅	∅

 이렇게 훨씬 간단해진 상태 전이표를 기반으로 다이어그램을 그릴 수 있을 것이다. ε-전이를 가지는 NFA와 ε-전이를 가지지 않는 NFA를 DFA로 변환하는 방법을 알아보았는데, 앞서 잠깐 도달 불가능한 상태를 없애 상태수를 줄일 수 있다고 하였다. NFA를 DFA로 변환한 것은 좋지만, 도달 불가능한 상태와 같이 의미없는 상태가 포함되어 있다면 이러한 상태들은 삭제시켜 주어야 한다. 다음 포스팅에서는 DFA의 상태수를 최소화하는 방법에 대해 알아보겠다.