9 - Regular Language (DFA State Reduction)

이번엔 DFA에서 State를 줄여나가는 방법이다.

 

 

먼저 state를 2개로 만든 모양이다.

빨간색 부분을 1구역, 파란색 부분을 2구역 이라고 보자.

 

1구역에는 A, B, D가 있고 2구역에는 C,E가 있다.

ABD는 각각 a 일때 1구역에 머물러있고, b 일때는 A는 1로, 나머지는 2구역으로 이동한다.

표로 정리하면 이렇게 된다.

a일 경우와 b가 같아야 한 state로 묶을 수 있으며, 현재 ABD state는 B,D경우가 다르므로

하나의 state로 만들 수 없다.

 

그러면 좀 더 쪼개서 3개의 state로 만들어보자.

구역을 3개로 나누어 보았다. 이렇게 되면 각 구역에서 선택지에 따라 일정한 곳으로 이동하게 된다.

이러한 식으로 정리가 가능하다.

그럼 각각 1, 2, 3을 다시 오토마타로 만들 수 있다.

 

2에서의 BD는 a,b에서의 상태가 같기 때문에 묶을 수 있고,

3에서 CE도 마찬가지로 a,b에서 상태가 같기 때문에 묶을 수 있는 것이다.