비결정적 오토마타의 시뮬레이션

비결정적 오토마타가 주어진 문자열을 수락하는지 알아보려면, 오토마타를 결정적 오토마타로 바꾸거나, 어떻게든 직접 해 보거나, NFA의 동작을 시뮬레이션하는 알고리즘을 쓸 수 있다.

알고리즘의 원리

원리를 알맞은 예로 알아보자. 다음 오토마타가 있다고 하자.

이 오토마타는 어떤 언어를 인식하는 비결정적 유한 오토마타이다. 그 언어가 무엇인지는 지금 전혀 중요하지 않다. 이런 오토마타의 계산이 입력 문자열 11001에 대해 어떻게 진행되는지 살펴보자. 생각은 이렇다. 문자열의 기호를 하나 처리하고, 같은 기호에 대한 다중 전이 덕분에 갈 수 있는 곳을 모두 찾는다. 이 상태들을 모두 기억해 두고, 다음 단계에서는 “이 상태들에 모두 동시에 있다”고 보고 이 상태들에서 다시 어디로 갈 수 있는지 알아본다.

따라서 지금 있을 수 있는 상태의 집합과 문자열에서 아직 읽지 않은 부분을 기억한다. 처음에는 순서쌍 ⟨{q₀}, 11001⟩이다. 상태 q₀(시작 상태)에서 출발하고 입력은 문자열 11001이다. 오토마타는 다음과 같다. 지금 있는 상태를 빨간색 굵은 선으로 표시했다.

첫 기호는 1이다. 상태 q₀에서 기호 1에 대한 전이는 하나뿐이므로 상태 q₁로 간다. 순서쌍 ⟨{q₁}, 1001⟩을 기억한다. 오토마타는 다음과 같다.

계속 진행한다. 아직 읽지 않은 부분은 1001이므로 다시 1에 대한 전이를 찾는다. 이번에는 전이가 두 개, 즉 상태 q₀으로 돌아가는 전이와 상태 q₃으로 가는 전이가 있다. 이제 두 상태로 동시에 간다. 따라서 순서쌍 ⟨{q₀, q₃}, 001⟩을 기억한다.

왜 이렇게 할까? 시작 상태에서 문자열 11로 상태 q₃에도, 상태 q₀에도 갈 수 있는 길이 있다는 것을 알고 있다. 어느 가지가 쓸모 있을지 아직 모르므로 둘 다 기억해 두는 것이다. 계속 진행한다. 입력 기호는 0이다. 이제 q₀에서 나가는 전이와 q₃에서 나가는 전이를 모두 살펴야 한다. 상태 q₀에서는 상태 q₁과 q₂로 가는 전이가 나가고, 상태 q₃에서는 다시 q₁로 가는 전이가 나간다. 이 상태들을 모두 모으면 순서쌍 ⟨{q₁, q₂}, 01⟩을 얻는다.

하지만 이 단계는 아직 끝나지 않았다. 상태 q₂에서 상태 q₄로 가는 ε 전이가 있다. ε 전이는 다음 문자를 읽지 않고도 “언제든지 따라갈 수 있다”. 다시 말해 입력 문자열에서 다음 기호를 읽지 않고도 상태 q₄로 더 옮길 수 있다. 그래서 있을 수 있는 상태에 상태 q₄를 더한다. 즉 ⟨{q₁, q₂, q₄}, 01⟩이다. 오토마타는 다음과 같이 칠해진다.

다음 입력은 0이다. 지금 있는 세 상태에서 어디로 갈 수 있는지 살펴본다. q₁에서는 0에 대한 전이가 없으므로 아무 데도 갈 수 없다. 이 가지의 계산은 여기서 끝난다. 상태 q₄에서도 아무 데도 갈 수 없다. 상태 q₂에서는 다시 상태 q₂로 간다. 그런데 상태 q₂에서 상태 q₄로 가는 ε 전이가 있으므로 상태 q₄에도 갈 수 있다. 따라서 상태의 집합 {q₁, q₂, q₄}에서 기호 0으로 상태의 집합 {q₂, q₄}에 갈 수 있고, 순서쌍 ⟨{q₂, q₄}, 1⟩을 얻는다.

마지막 입력은 기호 1이다. 상태 q₂에서는 아무 데도 갈 수 없으므로 이 가지의 계산은 끝난다. 하지만 상태 q₄에서는 상태 q₃과 q₅로 갈 수 있다. 순서쌍 ⟨{q₃, q₅}, ε⟩을 얻는다.

이제 오토마타는 문자열 전체를 읽었고 두 상태 q₃, q₅에 “있다”. 그중 적어도 하나가 수락 상태이므로 오토마타는 문자열 11001을 수락한다.

알고리즘

먼저 상태의 집합을 인자로 받아 ε 전이로 더 갈 수 있는 상태를 구하는 함수가 필요하다. 입력은 오토마타 ⟨Q, Σ, δ, q₀, F⟩와 상태의 집합 States이고, 출력은 이 상태들에서 ε 전이로 갈 수 있는 상태를 더한, 원래 집합을 포함하는 집합이다. 이 연산을 집합 States의 ε 폐포라고 한다.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

이 함수를 비결정적 오토마타의 동작을 시뮬레이션하는 함수에서 쓴다. 입력은 오토마타, 입력 문자열 w = w₁w₂… w_n, 오토마타가 지금 있는 상태의 집합이다. 출력은 오토마타가 주어진 문자열을 수락하는지에 따라 YES 또는 NO이다.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

오토마타가 문자열 w를 수락하는지 확인하려면 함수를 다음과 같이 호출한다: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

참고 자료

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

« 이전: 비결정적 유한 오토마타

다음: NFA를 DFA로 바꾸기 »