[Compiler] Subset Construction Algorithm (NFA ->DFA)

지난 포스트에서 Regular Expression을 Non-deterministic FA로 바꾸는 방법 중 가장 보편화된 방법인 Thompson's Construction Algorithm (TCA)에 대해서 간단한 예제를 통해서 살펴보았다. 그런데 사실 NFA를 구한 것 자체는 정답을 찾기 위해서 필요한 경우의 수를 추려놓은 정도이기 때문에 여기서 확실한 정답을 선별하기 위해서는 DFA로 바꿀 필요가 있다. 그래서 여기까지 하면 

Regular Expression

                                                                    | (Thompson`s Construction Algorithm)

                               Non-deterministic Finite Automata

                                                           | (Subset Construction Algorithm)

                        Deterministic Finite Automata

|

               Minimal Finite Automata

까지 마치게 될 것이다.

 자 다시 NFA와 DFA의 정의를 살펴보면 나올 수 있는 Finite input Set 인 Σ 에서 적절한 조합을 뽑아낸 것이 NFA인 것이고, 그걸 하나의 정답 형식으로 뽑아낸 값이 DFA가 된다. 그럼 다르게 표현하면 NFA는 하나의 집합 형태로 나열하면 그 안에 나올 수 있는 경우의 수를 표현할 수 있는 것이고, DFA는 그중 적절한 것만 선별하면 되는 것이다. 다음 예제를 살펴보겠다.

위와 같이 s는 a와 b의 concatenate된 형태를 띈다고 하자. 그러면 지난 포스트에서도 언급했다피 concatenate는 하나의 나열형식으로 표현된다. 여기서 initial state는 0 이므로 이때의 NFA는 {0} 일 것이다. 물론 단일 요소이기 때문에 DFA로 바꾼다 하더라도 0으로밖에 표현할 수 없다. 그럼 이후에 a라는 input string을 받게 되면 NFA로 표현할 수 있는 state는 어떻게 될까?경우의 수를 표현한 것이기에 하나의 set으로 표현하면 된다. 그럼 NFA는 {0,1} 이 될 것이고, 마찬가지로 DFA로 바꿔도 state 0에서 나갈 수 있는 state transition은 01로만 표현될 것이다. 

 이제 생각해볼 것은 input string으로 b를 받은 다음이다. b를 받고 난 후에는 2가지 branch transition이 발생한다. 그 상태에서 단지 ε 만 받더라도, 즉 아무 입력도 받지 않더라도 마음대로 state 2를 바꿀 수 있다. 이때의 NFA는 {2,3,4,0}이 될 것이고, 여기서는 DFA는  state 2에서 나갈 수 있는 transition도 2340, 023, 024... 등 여러가지로 뽑아볼 수 있을 것이다.  

 결론적으로 NFA를 DFA로 바꾼다는 의미 자체는 어떤 input string이 나왔을때 나올 수 있는 NFA의 요소들로 적절한 DFA의 state를 찾는다는 것이다. 그러면 NFA로 구성할 수 있는 부분집합들을 뽑아보면 DFA가 어떻게 나올지 유추할 수 있을 것이다. 이게 바로 Subset Construction Algorithm 또는 만든 사람의 이름을 따서 Büchi’s Algorithm 라고 한다. 일단 부분 집합의 이야기가 나왔으니까 특징을 말해보자면 N개의 state로 구성되어 있는 NFA가 있으면 그 NFA를 구성하는 부분집합 S는 반드시 N이 포괄하는 형태를 띌 것이고, 부분집합의 갯수는 공식에 따라서 2^N - 1로 표현할 수 있을 것이다. 따지고 보면 어마어마한 수일 수도 있지만 아무튼 finite 하기 때문에 DFA로 추출할 수 있다. 

 그러면 이 와중에 DFA를 추출하기 위해서는 어떤 방법을 해야 되냐 하는 의문이 생길 수 있는데 Subset Contruction Algorithm의 시작은 ε - closure에서 시작한다. 말 자체에서 의미하듯 Empty String ε 으로부터 transition할 수 있는 모든 set들이 다 ε - closure에 속하게 된다. 만약

  

state 2에서 ε 으로 갈수있는 state를 뽑아보면 3,4가 바로 옆에 있고, 한단계를 거쳐서 0 도 있을 것이다. 그래서

ε -closure({2}) = {2,3,4,0}  

 라고 표현할 수 있게 된다.물론 closure의 요소가 하나의 집합이 될 수도 있다.

  이렇게 구하면 앞에서 정의하던 NFA 추출방법을 단순히  ε 에 맞춰서 정하고 있다는 것을 알 수있다. 그러면 여기서 만약 다음 문자로 어떤 input string이 나올까 하는 가정을 집어넣게 된다면 우리가 원래 원하던 DFA의 진행 방향을 알 수 있을 것이다. 이 두가지가 바로 SCA에서 요구하는 것들이다. 현재 state에서 ε -transition으로 갈 수 있는 set들과 만약 현재 state에서 어떤 입력을 받을 경우의 set들을 정의하면 되는 것이다. 위에서 설명한 것들이 앞에서 잠깐 나왔던 ε -closure와 move(T,a)의 정의이다. 여기서 move(T,a)를 조금더 부연설명하자면 전체 state T에 속해있는 현재 state s에서 a를 입력으로 받았을 때 얻을 수 있는 NFA가 된다. 여기서 구한 값들을 이용해서 새로운 수식인 Dtrans 를 정의할 수 있게 된다.

Dtrans(T,a) = ε -closure(move(T,a)) 

    직역을 해보면 state T에 속하는 어떤 state s에서 입력을 a로 받았을 때 여기서 ε 으로 transition 할 수 있는 모든 state set을 나타내는 것이다. 지난 포스트에서 나왔던 예제를 가지고 적용해보고자 한다. 

여기서 관찰을 해보면 입력으로 줄 수 있는 것은 a와 b로 한정되어 있으며, 조금더 눈썰미가 있는 사람은 ε -closure(0) 을 구할 수 있을 것이다. 말 그대로 state 0에서 ε 로 transition 될 수 있는 state를 표현한 것이므로 {0,1,2,4,7}로 정의할 수 있을 것이며, 이걸 A라는 특정 set으로 정의한다. 그러면 위의 Dtrans 수식을 바로 적용해보면 A set에서 입력을 a로 받았느냐 b로 받았느냐에 따라서 정의할 수 있을 것이다. 

 - 입력을 a로 받았을 경우에는 Dtrans(A,a) = ε -closure(move(A,a)) 가 될 것이고, 이 말은 ε -closure({3,8}) 이라는 말과 같아질 것이다. 왜냐면 a를 받는 경우는 state 2에서 state 3로 넘어갈 때와 state 7에서 state 8으로 넘어갈 때에 대한 두가지 케이스이기 때문이다. 그러면 다시 ε - closure({3,8})= {1,2,3,4,6,7,8}로 정의할 수 있을 것이고 이걸 새로운 특정 set B로 정의를 한다.

 - 입력을 b로 받았을 경우는 Dtrans(A,b) =  ε -closure(move(A,b)) 가 될 것이고 앞에서 한 방법과 마찬가지로 ε -closure({5}) 라는 말로 바꿀 수 있을 것이다. 이러면 ε -closure({5}) = {1,2,4,5,6,7} 라고 할 수 있고 이를 또 C라고 정의한다.

이런식으로 계속 가지치기를 해 나가면 되는 것이다. 그러다보면 어느 순간에는 겹치는 set도 나올 것이고 이렇게 되면 더이상 transition할 여지도 없게 된다.이 때까지 계속 묶어나가는 방식이 바로 Subset Construction Algorithm의 개요다. 위의 예제에서 또 진행해보면 

 - Dtrans(B,a) = ε -closure(move(B,a)) = ε -closure({3,8}) = {1,2,3,4,6,7,8} = B

 - Dtrans(B,b) = ε -closure(move(B,b)) = ε -closure({5,9}) = {1,2,4,5,6,7,9} = D   

여기서도 새로운 Set D에 대한 정보를 얻었다. 

 - Dtrans(C,a) = ε -closure(move(C,a)) = ε -closure({3,8}) = B

 - Dtrans(C,b) = ε -closure(move(C,b)) = ε -closure({5}) = C

 - Dtrans(D,a) = ε -closure(move(D,a)) = ε -closure({3,8}) = B

 - Dtrans(D,b) = ε -closure(move(D,b)) = ε -closure({5,10}) = {1,2,4,5,6,7,10} = E       

 - Dtrans(E,a) = ε -closure(move(E,a)) = ε -closure({3,8}) = B

 - Dtrans(E,b) = ε -closure(move(E,b)) = ε -closure({5} = C       

로 정의할 수 있게 될 것이다. 위의 결과를 통해서 우리는 DFA Transition Table을 작성할 수 있게 되는 것이다. 

그러면 이걸 토대로 DFA Transition Diagram을 그릴 수 있을까? 말그대로 initial State를 A로 정의한 경우에는 다음과 같이 Diagram을 정의할 수 있게 되는 것이다.

이게 얼추 이 포스트의 서두에서 제시했던 NFA To DFA의 방법이다. 다시 NFA를 돌이켜 보자면

이랬었는데 위와 같이 DFA로 바꾸면 전체적인 State 수도 바뀌게 되고 불필요하게 state Number를 사용할 이유가 없어진 것이다. 궁극적으로 답에 조금씩 가까워진 것이다. 그런데 조금더 고민을 해보면 위에서 구한 DFA에서 더 줄일 수 있는 방법이 있다. 바로 같은 state를 merge 시키는 방법인데 이걸 보통 State Minimization Algorithm이라고 하고, 이렇게 구한 결과를 Minimal DFA라고 말한다. 이에 대한 이야기는 다음 포스트에서 계속하고자 한다.