불필요한 상태

유한 오토마타에는 수락 상태로 갈 수 없어서 쓸모없는 상태가 있을 수 있다. 이런 상태를 불필요한 상태라고 한다. 이런 상태는 오토마타 전체를 쓸데없이 복잡하게 만들 뿐이므로 보통 제거한다.

불필요한 상태의 예

다음 유한 오토마타가 있다고 하자.

상태 q₄나 q₅에 들어가면 그 뒤로는 수락 상태 q₁, q₂ 중 어느 것에도 절대 갈 수 없다. 따라서 이 상태들은 불필요하므로 그냥 제거할 수 있다. 그러면 새 오토마타를 얻는데, 이 오토마타는 원래 오토마타와 동치, 즉 같은 언어를 인식한다. 불필요한 상태를 지운 오토마타는 다음과 같다.

이 오토마타도 같은 언어를 인식한다. 하지만 불필요한 상태가 있는 편이 좋을 때도 있다. 예를 들어 완전 오토마타를 만들 때가 그렇다.

불필요한 상태의 정의

유한 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩가 있다고 하자. 다음을 만족하는 문자열 w ∈ Σ^∗와 상태 q_f ∈ F가 하나도 존재하지 않으면 상태 q ∈ Q는 불필요하다고 한다.

$$⟨q,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

불필요한 상태를 제거하는 방법

입력으로 이미 도달 불가능한 상태가 없는 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩가 주어졌다고 가정한다. 수락 상태로 가는 상태를 찾고, 그다음 수락 상태로 가는 상태로 가는 상태를 찾는 일을 계속 되풀이한다. 그러면 불필요하지 않은 모든 상태의 집합을 얻는다. 처음에 S₀ = F로 놓는다. i ∈ ℕ에 대하여 다음 규칙으로 집합 S_i를 차례로 만든다.

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

불필요하지 않은 모든 상태의 집합은 다음과 같이 나타낼 수 있다.

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

그리고 불필요한 상태의 집합은 다음과 같다.

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

다시 말해 S_i = S_{i + 1}이 성립하면 집합 Q ∖ S_i가 불필요한 상태의 집합이다. 이 방법을 다음 오토마타로 살펴보자.

먼저 S₀ = {q₁, q₂}로 놓는다. 다음으로 집합 S₀의 상태 중 하나로 가는 모든 상태를 집합 S₀에 더하여 집합 S₁을 만든다. q₀에서 q₁로 가는 전이가 있고 q₃에서 q₂로 가는 전이가 있으므로 상태 q₀과 q₃을 더한다. S₁ = {q₀, q₁, q₂, q₃}을 얻는다. S₀ ≠ S₁이므로 계속한다.

집합 S₂를 만든다. S₁로 갈 수 있으면서 아직 S₁에 없는 상태를 모두 찾는다. 그런 상태는 상태 q₃으로 갈 수 있는 q₆ 하나뿐이다. S₂ = {q₀, q₁, q₂, q₃, q₆}을 얻는다. S₁ ≠ S₂이므로 계속한다.

집합 S₃을 만든다. S₂의 상태 중 하나로 갈 수 있는 새 상태가 있을까? 없다. 상태 q₄와 q₅에서는 S₂의 어느 상태로도 갈 수 없고, 나머지 상태는 이미 S₂에 있다. 따라서 S₃ = {q₀, q₁, q₂, q₃, q₆}이다. S₂ = S₃이므로 알고리즘은 끝나고, 집합 S₂가 불필요하지 않은 상태의 집합이다. 집합 {q₄, q₅}는 불필요한 상태의 집합이다.

불필요한 상태가 없는 동치인 새 오토마타는 형식적으로 다음과 같이 만든다. 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩와 동치이고 불필요한 상태가 없는 오토마타 A′ = ⟨Q′, Σ, δ′, q₀, F⟩는 다음과 같다.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) (δ(q, a) ∈ Q′일 때). 그렇지 않으면 δ′(q, a)는 정의되지 않는다.

참고 자료

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools