오토마타의 최소화
오토마타의 최소화란 상태의 개수가 가장 적은 동치인 오토마타를 찾는 것이다. 불필요한 상태가 하나도 없는 오토마타도 더 간단하게 만들 수 있는 경우가 있다.
예
다음 오토마타를 보자.
이 오토마타는 문자열 01과 11만 수락한다. 같은 언어를 수락하면서 상태가 3개인 더 간단한 오토마타가 있다는 것은 분명하다. 상태 q1과 q2를 새 상태 {q1, q2} 하나로 합치고, 상태 q1이나 q2로 가던 전이는 새 상태로 가게 하며, q1과 q2에서 나가던 전이도 마찬가지로 처리한다. 그러면 다음 오토마타를 얻는다.
이 오토마타는 분명히 앞의 오토마타와 같은 언어를 수락하면서 상태는 더 적다.
동치인 상태
오토마타 A = ⟨Q, Σ, δ, q0, F⟩가 있다고 하자. 상태 q ∈ Q의 언어 L(q)를 다음과 같이 정의한다.
즉 오토마타 A의 시작 상태를 q0에서 q로 바꾸고, 이 오토마타가 인식하는 언어를 구한다. 다시 말해 언어 L(q)에는 오토마타 A에서 상태 q로부터 문자열 w를 읽어 오토마타의 수락 상태에 도달하는 모든 문자열 w가 들어 있다. 앞의 오토마타로 돌아가면 L(q1) = {1}이다.
서로 다른 두 상태 q1과 q2가 다음을 만족하면 두 상태는 동치라고 한다.
이 정의는 무슨 뜻일까? 상태 q1, q2가 동치이면, 이 상태들을 각각 오토마타의 시작 상태로 삼았을 때 같은 언어가 만들어진다. 다시 말해 오토마타가 형상 ⟨q1, w⟩와 ⟨q2, w⟩에 이르면 두 경우 모두 수락하거나 두 경우 모두 거부해야 한다.
앞의 오토마타로 돌아가면 상태 q1과 q2는 동치이다. 상태 q1에 있을 때는 아직 읽지 않은 부분이 1일 때만 입력 문자열을 수락할 수 있기 때문이다. 상태 q2에 있을 때도 마찬가지이다.
따라서 오토마타의 최소화는 동치인 상태를 찾고, 위의 예에서처럼 이 상태들을 새 상태 하나로 합쳐서 제거하는 것이다.
동치인 상태를 찾는 방법
어떤 상태들이 확실히 동치가 아닐까? 수락 상태와 비수락 상태는 확실히 동치가 아니다. 수락 상태의 언어와 비수락 상태의 언어가 다르기 때문이다. 수락 상태는 반드시 문자열 ε을 수락하지만 비수락 상태는 그렇지 않다. 방법을 예로 곧장 알아보자. 다음 오토마타가 있다고 하자.
먼저 상태의 집합 두 개를 만든다.
이제 전이표를 만들고, 그룹 S1과 S2에 대한 정보도 함께 적는다.
이제 표를 고친다. 주어진 기호에 대해 어느 상태로 가는지 직접 적는 대신, 가는 상태가 속한 그룹만 적는다. 예를 들어 상태 q3에서 0을 읽으면 그룹 S2에 속한 상태 q5로 간다. 그래서 표에 q5 대신 S2를 적는다.
이제 두 그룹을 다시 나눈다. 모든 기호에 대해 같은 그룹으로 가는 상태끼리 같은 그룹에 넣는다. 예를 들어 상태 q3과 q6은 0에 대해서도 1에 대해서도 같은 그룹으로 가지 않으므로 같은 그룹에 넣지 않는다. 반대로 상태 q1과 q2는 같은 그룹에 넣는다. 두 상태 모두 0에 대한 전이가 없고, 1을 읽으면 둘 다 그룹 S1로 가기 때문이다. 이렇게 새 그룹을 만든다.
각 그룹 안에서는 전이가 같다. 새로 생긴 그룹에 이름을 붙이고, 각 상태가 새 그룹 중 어느 그룹으로 가는지 다시 알아본다.
이제 그룹을 다시 나눈다. 그런데 더는 나눌 수 없고, 나누어도 같은 그룹이 나온다는 것을 알 수 있다. 상태 q1과 q2는 그룹 단위로 보면 전이가 같지만 이미 같은 그룹에 있고, 그룹 S4에는 다른 상태가 없기 때문이다. 동치인 상태를 찾는 알고리즘은 이것으로 끝난다. 각 그룹에서 상태를 하나만 고르고 나머지는 지운 다음, 지운 상태로 가던 전이는 모두 고른 상태로 가게 하면 된다.
예를 들어 새 오토마타의 상태를 q3, q6, q0, q1, q4로 하고 상태 q2와 q5를 제거하기로 하자. q2로 가던 전이는 모두 q1로 가고, q5로 가던 전이는 모두 q4로 간다.
오토마타의 최소화 과정
- 도달 불가능한 상태를 제거한다.
- 불필요한 상태를 제거한다.
- 동치인 상태를 제거한다.
참고 자료
목차: 도달 불가능한 상태, 불필요한 상태, 오토마타의 최소화