도달 불가능한 상태
유한 오토마타에는 도달할 수 없는 상태가 있을 수 있다. 이런 상태를 도달 불가능한 상태라고 한다. 이런 상태는 오토마타 전체를 쓸데없이 복잡하게 만들 뿐이므로 보통 제거한다.
도달 불가능한 상태의 예
다음 오토마타가 있다고 하자.
무엇을 하든 상태 q3에는 절대 도달할 수 없다. 이 상태로 들어가는 전이가 하나도 없기 때문이다. 그래서 상태 q3은 도달 불가능하다고 한다. 그렇다면 다른 상태에서 이 상태로 들어가는 전이가 있으면 상태 q3은 도달 가능할까? 상태 q0, q1, q2, q5 중 하나에서 간선을 그으면 도달 가능하다. 하지만 노드를 하나 더 추가하고 그 노드에서 전이를 그으면…
…당연히 상태 q3과 q4는 둘 다 도달 불가능하다.
도달 불가능한 상태의 정의
먼저 도달 가능한 상태를 정의한다. 유한 오토마타 A = ⟨Q, Σ, δ, q0, F⟩가 있다고 하자. 다음을 만족하는 문자열 w ∈ Σ∗가 존재하면 상태 q ∈ Q는 도달 가능하다고 한다.
상태 q ∈ Q가 도달 가능하지 않으면 도달 불가능하다고 한다.
도달 불가능한 상태를 제거하는 방법
오토마타에 도달 불가능한 상태가 있으면 제거하는 것이 좋다. 그래서 도달 불가능한 상태가 없는 동치인 오토마타 A′ = ⟨Q′, Σ, δ′, q0, F′⟩을 만든다.
도달 가능한 상태의 집합을 반복해서 만들어 간다. 시작 상태는 확실히 도달 가능하므로 집합 S0 = {q0}에서 시작한다. 다음 집합은 다음과 같이 만든다.
말로 풀면 다음과 같다. 집합 S0은 언제나 주어져 있다. 집합 S1은 집합 S0의 모든 상태에서 Σ의 모든 기호에 대한 전이가 어디로 가는지 모두 찾아서 만든다. 이 상태들과 원래 상태의 집합 S0의 합집합을 구한다. 같은 방법으로 집합 S2와 그다음 집합들을 구한다. 분명히 Si − 1 ⊆ Si가 성립한다.
그러면 도달 가능한 상태의 집합은 다음과 같이 얻을 수 있다.
무한히 많은 집합 Si의 합집합을 구하려는 것이 이상해 보일 수 있지만, 오토마타의 상태는 유한 개뿐이다. 따라서 어느 순간부터는 집합 Sj, Sj + 1과 그 뒤의 모든 집합이 같아지므로, 무한히 많은 집합의 합집합으로도 유한한 상태의 집합을 얻을 수 있다.
다음 오토마타로 돌아가
도달 가능한 상태의 집합을 구해 보자. 먼저 기본 등식을 놓는다.
이제 집합 S1을 구한다. 상태 q0에서 나가는 전이를 모두 찾아 그 도착 상태를 집합 S0에 더해야 한다. q0 → a q1이고 q0 → bq2이므로 집합 S1에는 상태 q1과 q2가 더 들어간다.
다음으로 집합 S2를 만든다. 상태 q0, q1, q2에서 갈 수 있는 곳을 모두 살펴본다. 새 상태는 상태 q1에서 갈 수 있는 q5뿐이다.
다음으로 집합 S3을 만든다. 상태 q0, q1, q2, q5에서 새 상태로 갈 수 있을까? 갈 수 없으므로 집합 S3의 원소는 S2의 원소와 같다.
S2 = S3이므로 S3 = S4 = S5 = …도 성립한다. 그 뒤의 어느 집합에도 새 원소가 더해지지 않으므로 모든 Si의 합집합을 구하면 집합 S2를 얻는다.
따라서 이 오토마타의 도달 가능한 상태의 집합은 {q0, q1, q2, q5}이다. 도달 불가능한 상태는 간단히 차집합으로 얻는다.
이 오토마타의 도달 불가능한 상태의 집합은 {q3, q4}이다. 오토마타 A에서 도달 불가능한 상태를 모두 제거하고, 도달 불가능한 상태가 포함된 전이도 모두 제거한다. 즉 오토마타 A = ⟨Q, Σ, δ, q0, F⟩와 동치이고 도달 불가능한 상태가 없는 오토마타 A′ = ⟨Q′, Σ, δ′, q0, F′⟩은 다음과 같이 정의한다.
- ∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a)