비결정적 유한 오토마타

앞에서 소개한 유한 오토마타(줄여서 FA 또는 DFA)는 언제나 결정적이었다. 즉 어느 순간에나 오토마타가 무엇을 할지 분명했다. 이제 더 일반적인 개념인 비결정적 유한 오토마타(줄여서 NFA)를 살펴보자. 비결정적 유한 오토마타에는 같은 상태에서 나가는, 같은 기호에 대한 전이가 여러 개 있을 수 있다.

예

다음 오토마타의 상태 전이도를 보자.

무엇이 특이할까? 노드 q₀에서 기호 0에 대한 간선이 두 개 나간다는 점이다. 그래서 문자열 001을 수락해 보려고 하면, 오토마타가 상태 q₀에 머물러야 할지 q₁로 가는 전이를 따라가야 할지 모르는 것처럼 보인다. 이런 오토마타가 비결정적 오토마타이다.

여기서 결정적이라는 것은 어떤 상황에서도 오토마타가 무엇을 할지 분명하고 모호함이 없다는 뜻이다. 결정적 오토마타에는 각 상태와 각 기호에 대해 전이가 하나뿐이다. 비결정적이라는 것은 모호하다는 뜻이다. 한 상태에서 같은 기호에 대한 전이가 예를 들어 3개 나갈 수도 있다.

그러면 오토마타는 어떻게 결정할까? 비결정적 오토마타는 가능하다면 언제나 문자열을 수락하게 되는 전이를 고른다(“알아맞힌다”고도 한다).

오토마타에 문자열 001을 넣으면 오토마타가 문자열을 처리하는 방법은 다음과 같다.

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

여기에 문자열 전체를 읽지 못하는 경우가 더 있다. 첫 번째 경우에는 줄곧 상태 q₀에 머물렀는데, 전이 규칙이 이를 허용하므로 당연히 가능하다. 두 번째 가지에서는 과감하게 다른 상태로 나아가 마침내 수락 상태인 상태 q₂에 도착했다. 이 가지에서는 오토마타가 문자열을 수락한다. 비결정적 오토마타는 문자열을 수락하는 가지가 있으면 언제나 저절로 그 가지를 고른다.

어떻게 “유리한” 가지를 저절로 고를까? 비결정적 오토마타가 가능한 모든 가지를 살펴보고, 문자열을 수락하는 가지를 찾으면 문자열을 수락한다고 생각하면 된다. 모든 가지를 어떻게 살펴볼까? 현재 기호에 대한 간선이 n개 나가는 상태에 있을 때 오토마타는 자기 자신을 n개 복사하고, 각 복사본이 서로 다른 길로 간다. 이렇게 하면 모든 가능성을 차례로 살펴볼 수 있다.

오토마타의 계산 트리

앞의 오토마타를 조금 바꿔 보자.

비결정성은 첫 번째 상태에 그대로 있다. 앞의 오토마타는 01로 끝나는 모든 문자열을 수락했다. 바꾼 오토마타는 부분 문자열 01을 포함하는 모든 문자열을 수락한다. 따라서 예를 들어 문자열 101이나 0101을 수락한다. 계산의 모든 가지는 트리로 쉽게 나타낼 수 있다. 예를 들어 문자열 01010에 대한 트리는 다음과 같다.

처음에는 시작 상태 q₀에 있다. 입력은 문자열 01010이고 아직 읽지 않은 첫 문자는 0이다. 상태 q₀에서 기호 0에 대한 전이가 상태 q₀과 q₁로 두 개 나간다. 그래서 트리의 이 노드에는 두 자식 q₀과 q₁이 생긴다. 다음으로 기호 1을 읽는다. 여기에는 모호함이 없으므로 상태 q₀과 q₂로 옮긴다. 다음으로 문자 0을 읽으면 왼쪽 가지에서 다시 모호함이 생기므로 계산을 다시 두 가지로 나눈다. 한 가지에서는 다시 q₀에 머물고 다른 가지에서는 q₁로 간다. 이런 식으로 계속한다.

수락 상태인 상태 q₂에서 끝나는 가지가 모두 두 개라는 점에 주목하자. 오토마타가 주어진 문자열을 수락하는 계산의 가지가 두 개 있다. 따라서 이 오토마타는 문자열 01010을 수락한다. 문자열 1000에 대해서도 같은 트리를 만들어 보자.

계산은 상태 q₀에 머물거나 상태 q₁로 가는데, 그 상태에서는 더 갈 곳이 없다. 입력에는 0만 남아 있고 상태 q₁에는 기호 1에 대한 전이만 있기 때문이다. 수락 상태에서 끝나는 계산의 가지가 없으므로 오토마타는 문자열 1000을 수락하지 않는다.

ε 전이

비결정적 오토마타에서는 ε 전이도 쓸 수 있다. ε 전이는 입력 기호가 무엇이든, 문자열에서 기호를 읽지 않고도 할 수 있는 전이이다. 빈 문자열, 1로만 이루어진 모든 문자열, (10)ⁿ 꼴의 문자열, 즉 10, 1010, …을 수락하는 비결정적 오토마타는 어떻게 만들 수 있을까?

오토마타를 두 “부분 오토마타”로 나누었다. 위쪽은 1로 이루어진 문자열을 인식하고, 아래쪽은 (10)ⁿ 꼴의 문자열을 맡는다. 문자열 111을 수락해 보자. 오토마타는 처음에 상태 q₀에 있고 입력은 문자열 111이다. ε 전이를 쓸 수 있으므로 형편에 따라 상태 q₁이나 q₂로 가기로 결정할 수 있다. 여기서는 상태 q₁로 가는 것이 유리하다는 것을 알 수 있다. 오토마타는 그 상태로 간다. 이때 입력은 여전히 문자열 111이다! 이제야 문자열의 기호를 읽기 시작하여 상태 q₁에서 다시 q₁로 가고, 문자열 전체를 읽은 뒤 문자열을 수락한다.

1010을 수락해 보면 오토마타는 처음에 상태 q₂로 가고, 거기서부터 기호를 처리하기 시작하여 역시 문자열을 수락한다.

문자열 1100은 오토마타가 무엇을 하든 수락할 방법이 없다.

ε 전이와 비결정성은 여러모로 일을 쉽게 해 준다. 예를 들어 정규 언어의 합집합이 다시 정규 언어라는 증명은 결정적 유한 오토마타로 할 때보다 ε 전이를 쓰면 훨씬 간단하게 쓸 수 있다. 그 증명에서는 다음 오토마타들을 예로 들었다.

그리고

이어서 두 언어의 합집합을 인식하는 결정적 유한 오토마타를 만들었다. ε 전이를 쓰면 그런 오토마타를 다음과 같이 만들 수 있다.

새 시작 상태를 추가하고, 그 상태에서 원래 두 오토마타의 시작 상태로 가는 ε 전이 두 개를 두면 끝이다. 오토마타는 어느 “부분 오토마타”로 문자열을 수락해 볼지 비결정적으로 정한다.

비결정적 오토마타의 정의

결정적 유한 오토마타와 비결정적 유한 오토마타가 어떻게 다른지 살펴보았으니, 이제 이를 형식화하기만 하면 된다. 결정적 유한 오토마타는 5-튜플 ⟨Q, Σ, δ, q₀, F⟩로 정의했다. 여기서 Q는 상태의 집합, Σ는 알파벳, δ는 전이 함수, q₀은 시작 상태, F는 수락 상태의 집합이다. 비결정적 오토마타의 정의에서 달라지는 것은 전이 함수의 정의뿐이다.

결정적인 경우 함수는 호출 δ(q, w)에 대해 상태를 하나만 돌려줄 수 있었지만, 비결정적인 경우에는 한 기호에 대한 전이가 여러 개 정의되어 있으면 상태를 여러 개 돌려줄 수 있다. ε 전이도 정의해야 하므로 집합 Σ ∪ {ε}을 Σ_ε으로 나타내자. 즉 Σ_ε = Σ ∪ {ε}이다. 그러면 함수 δ는 다음과 같이 정의한다.

$δ : Q \times Σ_{ε} \to 2^{Q}$

여기서 2^Q은 멱집합, 즉 집합 Q의 모든 부분집합의 집합을 뜻한다. 계산의 형식화는 유한 오토마타의 경우와 매우 비슷하다. 오토마타의 형상은 여전히 순서쌍 ⟨q, w⟩ ∈ Q × Σ^∗이다. 계산 단계 ↦는 형상의 집합 위의 관계로, q_j ∈ δ(q_i, w₀)일 때, 그리고 그때에만 다음이 성립한다.

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

가장 크게 달라진 곳이 이 문장이다. 결정적 오토마타에서는 함수 δ가 언제나 상태 하나를 돌려주므로 이 조건을 q_j = δ(q_i, w₀)으로 썼다. 비결정적인 전이 함수는 상태의 집합을 돌려주므로 기호 ∈을 쓴다. 이 관계의 반사적·추이적 폐포도 마찬가지로 ↦ ^∗로 나타낸다. 다음을 만족하는 q_f ∈ F가 존재할 때, 그리고 그때에만 오토마타가 문자열 w를 수락한다고 한다.

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

참고 자료

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

« 이전: 완전 오토마타

다음: 비결정적 오토마타의 시뮬레이션 »