[Compiler] NFA / DFA

지난 포스트를 통해서 Finite Automata를 잠깐 언급했다. 사실 써놓고 무슨 내용인지는 나 자체도 이해가 안가지만 특정 문구를 뽑아내기 위한 Regular Expression이 나오면 이를 Finite State 형태로 구현하는 것 자체가 Finite Automata 라고 했던 것 같다. 

즉, 오른쪽의 수식을 하나의 State Diagram으로 변환해주는 과정 자체가 Finite Automata를 구현하는 단계라고 볼수 있다. 위의 수식은 표현하자면 state를 나눠놓고 0일때의 입력이 어떻게 들어왔느냐에 따라서 state의 변화 정도를 표현한 것이다. 예를 들어 첫번째 입력이 a로 들어오면 b가 들어올때까지 state가 유지되는 것이다. Regular Expression 식도 그 이전 포스트에서 다뤘던 kleene star의 정의를 되집어 보면 나올 수 있는 결과물이 {b, ab, aab, aaab, ....} 등이라는 것을 확인할 수 있다.

 그럼 이 Fintie Automata를 구성하는 요소, 다시말해 어떤게 있어야 왼쪽의 이미지를 그릴 수 있을까? 당연한 이야기이겠지만 처음 state와 나올 수 있는 state 들도 있어야 표현할 수 있을 것이다. 그리고 각 state에서 넣을 수 있는 입력들도 FA의 구성 요소가 될 수 있다. 물론 Empty string ε 도 포함할 수 있다. 그러면 시스템의 정의 상 입력과 state가 나온 이상 하나의 Transition Function으로 표현할 수 있다. 수식으로는 다음과 같다. 

f : S * ( Σ ∪ ε )

S = finite set of States

Σ = a set of input Symbols

위 수식이 의미하는 건 결론적으로 앞에서 언급했던 것처럼 같은 state이더라도 입력이 어떻게 되냐에 따라서 Transition이 바뀌는데 그걸 수식으로 표현할 수 있다는 것이다. 그러면 이식을 통해서 현재 state에 들어올 입력과 다음 state의 가능성을  충분히 보여줄 수 있을 것이다. 

 여기서 질문을 던져 볼 수 있다. 과연 현재 state와 다음 state간의 transition을 위와 같이 정의했으면 다음 state를 알았을 때 이전 state에 대해서 확신할 수 있느냐는 것이다. 

 위와 같이 Transition Diagram이 그려져 있다. 분명 S1에서 어떤 입력을 받게 되면 final state인 s3 혹은 s5로 transition 될 것이다. 그런데 이런 궁금증이 생길 수 있다. start state인 s0에서 b라는 입력이 들어오면 state가 어떻게 변할까... 답은 알 수 없다. 반대로 어떤 state에서 입력으로 b를 넣으면 state가 s1으로 바뀌느냐... 적어도 위의 그림에서는 알 수 없다. 다만 확실한 것은 s1에서 어떤 입력을 넣으면 final state에 이른다는 것이다. 그런데 여기서도 반대로 어떤 입력에 b를 넣으면 s3가 될 수 있느냐에 대한 답을 찾을 수 없다. 이처럼 state에 대한 불확실성이 담긴 것을 여기서는 deterministic 이란 개념으로 설명한다. 즉, 입력과 final state에 대한 정보를 통해서 이전 state에 대해 확신을 할 수 있으면 Deterministic Finite Automata (DFA), 확신이 없으면 Non-deterministic Finite Automata (NFA) 라고 말한다. 

 결국 이 정의에 따르면 위의 그림은 현재 state에 대한 확신이 없는 NFA 방식의 Diagram이다. 쉽게 말해서 Finite State까지 이르는데에 대한 가능성만 보여주고 있는 것이다. 그렇기 때문에 현재 있는 state 자체가 정확한 state라고 확신할 수 없는 것이다. 만약 결과론적으로 보자면 사실 s0s1s2s3나 s0s1s4s5나 똑같다. 어느 길을 수행하든 Finite Automata는 끝났다는 결과물을 보여줄 것이다. 하지만 우리가 Lexical Analysis에서 추구하는 것은 어휘 하나하나를 분석해서 특정 단어에 대한 정의를 수행하는 것이기 때문에 그 state transition 과정 자체도 중요하다. 물론 방식 자체도 가능성이라는 큰 맥락을 잡는 것이기에 답을 찾는데 유용하게 사용할 수 있다. 그래서 보통 compiler의 첫번째 단계인 Lexical Analysis는 다음과 같은 세부 과정을 거치게 된다.

Lexical Specification

|

Regular Expression

|

Non-deterministic Finite Automata (NFA)

|

Deterministic Finite Automata (DFA)

|

Minimal Deterministic Finite Automata (minimal DFA) 

or Table Driven DFA Implementation 

|

Generate Scanner

결론적으로 우리가 Lexical Analysis를 하는 최종 목적은 DFA를 최소화 시킨 Minimal DFA를 통해서 Scanner를 구하는 것이 된다. 다시 설명하자면 NFA를 통해서 답에 대한 확률적인 가능성을 발견하면 이를 DFA로 변환하고 축약하는 과정을 거쳐야 비로소 Lexical Analysis가 마무리 되는 것이다. 약간의 감이 안 잡힐 수도 있겠지만, 일련의 과정을 거치면서 그 중간 단계를 쉽게 처리할 수 있는 알고리즘들이 나와있으며, 학부 컴파일러 수업에서는 이걸 실제로 적용해보는 문제를 많이 푸는 것 같다. 아무튼 변환 과정은 다음 포스트에서 설명하고 그럼 NFA와 DFA의 차이를 알아보는게 진행될 내용일 듯 하다.

 가장 큰 차이는 하나의 state가 몇개의 transition을 가지냐는 것이다. 앞의 예시에서 보다시피 NFA는 하나의 state에 관해서도 여러개의 transition을 가질 수 있다. 즉, 이전에 설명했던 것처럼 가능성에 대해서 모두 제시한 것이기 때문에 가능한 것이다. 또한 가능성을 기반으로 FA가 구성되었기 때문에 상황에 따라서는 설명이 안되는 transition 이 등장하기도 한다. 보통 그런 것을 ε - transition이라고 한다.   반면 DFA는 하나의 state에 대해서 딱 한개의 transition만 가진다. 그리고 모든 state에 대해서 transition이 명확하기 때문에 NFA에 나왔던 ε - transition은 존재하지 않는다. 

결론적으로 NFA를 통해서는 possible state transition을 구할 수 있고, DFA를 통해서는 확실한 정답을 유추할 수 있다는 것이다. 한가지 예를 들어보자. 

Lexical Analysis를 통해서 (a|b)*abb라는 Regular Expression을 얻었다. 여기서 aababb라는 답을 얻으려면 어떻게 해야 될까? 먼저 NFA를 통하면 다음과 같이 Diagram을 그릴 수 있다.

NFA에서는 aababb를 얻기 위한 모든 과정을 나열해본다. 그래서 모든 과정 중에서 답이라고 생각되는 것들을 선택하는 방식이다. 그러면 위의 방식대로 subset을 구해보면 aaaaaaaaaaababb도 NFA에서는 어쩌면 답이라고 인식할 수 있을 것이고, 또는 abbababb도 답이라고 생각할 수 있다. 이 모든게 하나의 답을 위한 subset으로 표현될 것이다. 이렇게 되면 input에 대한 state transition도 하나의 subset으로 표현할 수 있을 것이다. 

 하지만 DFA라면 그야말로 앞에서 주어진 RegularExpression으로부터 답을 명확하게 뽑아낸 것이다. 그러면 다음과 같이 표현될 것이다.

여기서 나올 수 있는 state transition은 {s0s1s1s2s1s2s3} 딱 하나이다. 그냥 이걸 분석하면 우리가 찾고자하는 aababb라는 답을 찾을 수 있는 것이다. 여기서 NFA와 DFA의 차이를 알아볼 수 있다. 

확실히 DFA는 답을 유추하는데 있어서 단하나의 state transition을 수행하면 되기 때문에 Lexical Analysis 내에서 처리 속도가 빠르다. 하지만 딱 보이다시피 하나의 subset이 여러개의 state가 주렁주렁 매달려있는 꼴이다. 물론 지금이야 단 6개의 알파벳을 바탕으로 답을 찾는 과정이기 때문에 별차이가 없어지지만 실제 compiler내에서의 DFA로 동작할 때는 state가 훨씬 더 많아 질 수 있다. 반면 NFA는 여러개의 possible을 일일히 고려해야 되기 때문에 당연히 DFA에 비해서 처리속도가 느리다. 하지만 위의 그림에서도 단적으로 보여지는 것처럼 DFA에 비해서 표현하는 state가 적다. 이 때문에 construction 시에도 NFA들이 조금더 작게 표현된다. 이처럼 space와 time내에서 trade off가 발생한다. 그래서 Lexical Analysis시 NFA를 수행해서 전체 Area를 줄인 뒤에 DFA를 통해서 수행 시간을 줄이는 것이 일반적인 처리 방식이다.