[Compiler] DFA -> Minimal DFA : State Minimization Algorithm

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다.

 

출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler

 

 

이전 시간에 NFA에서 DFA로 변환하는 과정을 알아보았다.

 

 

위 그림을 기억하는가?? 오류가 있는데 위 그림에서 e가 완료 상태이다.

이 그림에서 상태 a가 initial state로 정해져 있지만, a에서 입력으로 A, B로 받는것과 c에서 입력을 A,B로 받는 것이 결과가 같다. 시작 상태가 c여도 똑같을 것이다. 

 

이처럼 Subset Construction Algorithm은 표현할 수 있는 모든 경우의 수에 대해 DFA를 구한 것이기 때문에 불필요한 State Transition이 표현되기도 한다. 이 불필요한 상태를 합치는 것이 Minimal State DFA가 될 것이고, 같은 Language로 구현된 DFA는 무조건 축약이 가능하다에서 시작한다.

 

축약을 하기 위해 가능한지를 먼저 살펴본다. 이 distinguishable을 위해 구별 불가능한 state만 묶어서 single state로 만드는 방법이 여기서 사용할 State-Minimiztion Algorithm이다. 이 과정을 모두 거치면 Lexical Analysis가 끝난다.

 

state s에서 t로 넘어갈 때 x라는 string이 유일한 경우에 x를 distinguishable하다 라고 한다.

즉, 두 state를 이어주는 transition간에 중복되는 string이 없어야 한다.  상태 a에서 BA를 통해 갈 수 있는 state가 B가 될 수 있고, c에서도 같은 입력을 통해 b에 갈 수 있다. 이것이 Undistinguishable이다.

BB를 가지고 b,c를 비교하면 서로 다른 곳으로 이동한다. 이것이 distinguishable이다. 이같은 구분을 Partition이라 하며, 이 작업을 쪼갤 수 없을 때까지 수행하는 것이 State-Minimization Algorithm이다.

예시를 보며 따라가보자.

 

 

 

 

그림에서 E가 완료상태이다.

우선 그림처럼 Patrition을 Accepting state와 non Accepting state로 묶을 수 있다. 그러면 {{a,b,c,d},{e}} 로 나눌 수 있다. 이중 e가 포함되어 있는 set은 e 하나이기 때문에 분해할 partition이 없다. 이제 e를 제외하고 {a,b,c,d} 에 대해 Partition 분해를 해보자. 이전 포스트의 Subset Construction Algorithm 방식처럼 하나의 입력을 대입하며 Partition을 만든다.

 

입력 A에 대해 각 상태에서 A를 사용하면 갈 수 있는 공통적인 state가 b가 된다. 즉 A는 a,b,c,d에 대해 distinguish하지 않다. 입력 B를 따지면 {a,c} 에서는 B를 사용해서 c, b에서는 d로 갈 수 있다. 하지만, d에서는 b를 사용하면 외부 Partition인 state e로 간다. 

이것을 Partition하면 {a,b,c} 와 {d}로 구분 할 수 있다. 결국 {a,c},{b},{d}.{e} 로 구분할 수 있다.

{a,c}는 어떠한 입력에 대해 distinguish하지 않다. a나 c 어떤 걸 사용해도 Minimal DFA를 구하는데 차이가 없다. 

이것을 바탕으로 새로 Diagram과 Transition Table을 작성한다.

 

위와 같은 결과가 나온다. state와 transition이 제거되면서 간소화했다. 이전 포스팅의 DFA와 비교해보면 좋을 것 같다. 이러한 축소작업을 통해 연산 하나하나의 cost가 줄어들기에 중요함을 알고만 가자.