이 글은 을 참고하여 만들어졌습니다. 3.3.4 DFA의 상태수 최소화DFA의 상태수 최소화(state minimization)는 DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임으로써 기억 공간을 적게 차지하도록 하고 또한 어휘 분석 프로그램을 간단히 하는데 큰 도움을 준다.상태수를 최소화하는 방법은 등치 관계(equivalence relation)을 이용하여 상태들을 합침(state merge)으로써 상태수를 최소화하는 것이다.따라서 구별되지 않는 상태들은 같은 형태의 입력 스트링을 인식하기 때문에 모두 합칠 수 있다.다음은 동치 관계를 이용하여 구별되지 않는 상태들을 하나의 상태로 합치는 방법이다. DFA의 상태 집합을 동치 관계에 의해 분할하고 각 동치류를 최소화한 유한 오토마타 상태(Q..
