완전 오토마타

유한 오토마타의 기본 정의에서는 모든 상태에서 모든 기호에 대한 전이가 있을 필요가 없다. 완전 오토마타는 모든 상태에서 입력 알파벳의 모든 기호에 대한 전이가 정의된 오토마타이다.

완전 오토마타를 만드는 방법

다음 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩가 있다고 하자.

여기에는 상태 q₀에서 글자 “b”에 대한 전이가 그려져 있지 않다. 이런 상황이 생기면 오토마타는 그 입력 문자열을 수락하지 않는다고 한다. 하지만 형식화의 관점에서는 전이 함수 δ가 일부 값에서 정의되지 않는 것이 바람직하지 않을 수 있다. 여기서는 예를 들어 δ(q₀, b)가 정의되어 있지 않다.

이 문제는 상태가 하나 더 많은 동치인 오토마타를 만들면 쉽게 해결된다. “빠진” 전이는 모두 이 상태로 가게 하고, 이 상태는 수락 상태가 아니며, 그 뒤의 모든 입력에 대해 이 상태에서 계속 맴돌게 한다. 이렇게 만든 오토마타를 완전 오토마타라고 한다. 고친 동치 오토마타는 예를 들어 다음과 같다.

상태 q_fail을 추가했다. 다른 상태에서 이 상태로 가는 전이는 원래 전이가 없던 곳에만 추가했다. 이 상태는 수락 상태가 아니고, 그 뒤의 모든 입력에 대해 자기 루프를 돈다. 앞의 오토마타에서 빠진 전이를 만났던 곳에서도 이 오토마타에는 빠진 전이가 없고, 오토마타는 상태 q_fail로 간다.

따라서 일반성을 잃지 않고 언제나 오토마타가 상태와 알파벳 글자의 모든 조합에 대해 전이가 정의되어 있다고 가정할 수 있다.

정의

완전 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩에 대하여 다음이 성립한다.

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

참고 자료

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