[Compiler] State Minimization Algorithm (DFA -> Minimal DFA)

지난 포스트에서 NFA에서 DFA로 구하는 변하는 과정을 알아보았다. 그래서 최종적으로 나온 결과는 다음과 같다.

그런데 유심히 살펴보면 뭔가 이상한 점이 있다. A가 initial state로 정해져 있긴 하지만 A에서 입력을 a,b로 받는 거나, C에서 a,b로 입력을 받는 것이나 결과가 똑같다. 만약 initial State가 C로 되어 있더라도 위와 별반 차이가 없을 것이다. 이처럼 Subset Construction Algorithm은 표현할 수 있는 모든 경우의 수에 대해 DFA를 구한 것이기 때문에 간혹 불필요한 State Transition이 표현되어 있기도 하다. 그래서 조금 더 노력해보면 이 state들을 합칠 수 있다는 결론을 내릴 수 있다. 이렇게 축약한 결과가 Minimum State DFA가 되는 것이고, 기본적인 전제는 같은 language로 구현된 DFA는 무조건 축약이 가능하다는 것에서 시작한다. 

 아무래도 축약을 하기 위해서는 축약이 가능한가, 가능한지 않은가를 구별할 수 있어야 한다. 말그대로 distinguishable을 따지는 것이다. 이중 undistinguishable한 state만 묶어서 single state로 만드는 방법이 바로 State-Minimization Algorithm이 되는 것이다. 여기까지 거쳐야 비로소 Lexical Analysis가 끝나게 되는 것이다. 물론 이를 코드로 구현하는 큰문제가 남아있긴 하지만 Lexer라고 이런 걸 해주는 툴을 만들어놨다. 참 대단한 사람들이다...

  아무튼 Distinguishable을 가리는 기준은 dragon 책에는 다음과 같이 명시되어 있다.

 - String x distinguishes state s from state t if only one of the states reached from s and t by following the path with label x is an accepting state

즉, state s에서 t로 넘어갈 때 x라는 string이 유일한 길일 경우에 x를 distinguishable 하다라고 언급하는 것이다. 그말은 즉, 두 state를 이어주는 transition간에 중복되는 string이 없을 경우에 서로 다르다고 할 수 있을 것이다. 예를 들어서 string ba를 척도로 A와 C를 비교해보자

 그럼 A에서 ba를 이용해서 갈 수 있는 state는 B가 될 수 있고, C에서도 ba를 이용해서 B에 갈 수 있다. 이같은 경우가 Undistinguishable한 case이다. 반면 string bb를 가지고 B와 C를 비교해보면 B에서는 E로만 갈수 있고, C의 경우에는 C내에서만 이동할 수 있다. 이때가 바로 Distinguishable한 경우가 될 것이다. 이렇게 구분을 짓는 것을 일종의 partition이라고 한다. 이 partition을 치다보면 점점 작은 subgroup으로도 쪼갤 수 있고, 더 이상 subgroup으로 쪼갤 수 없을 때까지 계속 수행하는 것이 State-Minimization Algorithm의 동작이라고 할 수 있겠다. 

그럼 위의 예제를 그대로 이 방법에 적용시켜보겠다.

 일단 첫번째 partition은 accepting state냐 non-accepting인가로 묶을 수 있다. 그러면 

아래와 같이 하나의 Set으로 묶을 수 있고 이와중에 Final State인 Accepting State를 구할 수 있을 것이다. 그래서 첫번째 partition은 

{{A,B,C,D},{E}} 로 나눌 수 있을 것이다. 이중 E가 포함되어 있는 set은 E 딱 하나이기 때문에 이제 분해할 partition이 없게 된다. 이런건 따로 빼주고 나머지 A,B,C,D에 대해서 또 Partition을 분해해보면 된다. 여기서도 이전 포스트의 Subset Construction Algorithm 방식처럼 하나의 입력을 대입해보면서 partition을 만들면 된다. 

 먼저 입력 a에 대해서 생각해보면 각 state에서 a를 사용하면 갈수 있는 공통적인 state가 B가 됨을 알 수 있다. 이말은 앞에서 말한 표현을 따르자면 a는 A,B,C,D에 대해서 distinguish하지 않다는 말이 된다. 그래서 구별하기에는 부족한 요소가 된다. 다음 입력 b에 대해서 따져보면 {A,C}에서는 b를 사용해서 C로 갈 수 있고, B에서는 b를 이용해서 D로 갈 수 있다. 그런데 D에서는 b를 사용하면 같은 Non-Accepting State가 아닌 외부의 state인 E로밖에 갈 수 없다. 이때 또 partition을 치면 {A,B,C}와 {D}로 구분할 수 있다. 이런식으로 partition을 치다보면 최종적으로는 

{A,C},{B},{D},{E}

 이렇게 구분지을 수 있고, 더이상 나눌 여지가 없어진다. 결국 A,C는 어떠한 입력에 대해서도 Distinguishable 하지 않다는 결론을 얻게 된다. 그냥 간단하게 말하면 A나 C 어떤 걸 써도 minimal DFA를 구하는데 차이가 나지 않는다는 것이다. 그럼 Diagram과 Transition Table을 다시 작성할 수 있게 된다. 

다시 돌아가서 DFA의 Diagram과 Table을 돌아보자.

확실히 state가 하나 사라지면서 transition이 하나 줄고, 덕분에 Diagram도 조금 간소화해졌다. 사실 이렇게 줄이는 이유 자체는 앞의 NFA와 DFA의 차이에서도 잠깐 설명했던 걸 적용해볼 수 있다. NFA가 가진 장점을 DFA에 적용시킬 수 있다는 측면에서 이 State Minimization Algorithm은 Lexical Analysis 내에서의 optimization이라고 생각한다. 이게 중요한 이유는 이런 연산 하나하나가 Cost로 직결되기 때문이다. 사실 이 Cost를 적용하기 위해서는 Big O notation같은 Complexity를 계산해야 되는데 여기까지는 아직 내공이 부족해서 이만...