[Compiler] NFA/DFA

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

 

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

 

FA는 특정 문구를 뽑아내기 위한 Regular Expression이 나오면 이를 Finite State 형태로 구현하는 것 자체가

Finite Automata 라고 한다.

어떤 수식을 하나의 state Digram으로 변환해주는 과정 자체가 Finite Autoata를 구현하는 단계라고 생각하면 된다.

 

EX) 

a∗b -> {b , ab, aab, aaab ...} 등이라는 것을 확인할 수 있다. 

 

이 Finite 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로 변한다. 

만약 S0에서 b라는 입력이 온다면??? 답은 알 수 없다. 반대로,

어떤 state에서 입력으로 b를 넣으면 state가 s1로 바뀌는가? 적어도 위 그림에서는 알 수 없다.

확실한건 S1에서 어떤 입력을 넣으면 Final State에 이른다는 것이다.   

여기서 어떤 입력에 b를 넣으면 S3이 되는가에 답 또한 알 수 없다.

이처럼, 입력과 Final state에 대한 정보를 통해 이전 State에 대해 확신을 할 수 있으면

Deterministic Finite Automata(DFA), 확신이 없다면 Non-Deterministic Finite Automata(NFA) 라고 한다.

 

위 그림은 현재 state에 대한 확신이 없는 NFA 방식이다. Finite State까지 이르는데에 대한 가능성만 보여주고 있다.

그렇기에 현재 있는 state 자체가 정확한 state라고 확신할 수 없는 것이다.

우리가 Lexical Analyis에서 추구하는 것은 어휘 하나하나를 분석해 특정 단어에 대한 정의를 수행하는 것이기 때문에 그 state transition과정 자체도 중요하다. 컴파일러의 첫번째 단계인 Lexical Analysis는 아래의 세부과정을 거친다.

 

Lexical Specification -> Regular Expression -> NFA -> DFA -> Minimal DFA or Table Driven DFA -> Generate Scanner

 

결국 Lexical Analysis의 최종 목표는 DFA를 최소화 시킨 Minimal DFA를 통해 Scanner를 구한는 것이다.

NFA를 통해 답에 대한 확률적인 가능성을 발견하면 이를 DFA로 변환하고 축약하는 과정을 거쳐 Lexical Analysis가 끝난다. 여기서 NFA와 DFA의 차이를 좀 더 알아보자

 

가장 큰 차이는 하나의 state가 몇개의 transition을 가지냐는 것이다. NFA는 하나의 state에 관해 여러개의 transition을 가질 수 있다. 가능성에 대해 모두 제시하기 때문에 그렇다. 이 가능성을 기반으로 FA가 구성되었기 때문에 상황에 따라 설명이 안되는 transition이 등장하기도 한다.
DFA는 하나의 state에 대해 하나의 transition만 가진다. 그리고 모든 state에 대해 transition이 명확하다.

 

결론적으로 NFA를 통해 Possible state transition을 구할 수 있고, DFA를 통해 확실한 정답을 유추할 수 있다.

Lexical Analysis를 통해 Regular Expression인 (a|b)*abb 라는것을 얻었고 aababb라는 답을 얻기위해 아래의 NFA를 통한 Digram을 그릴 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

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

 

DFA라면 앞의 Regular Expression으로부터 답을 명확히 뽑아야 한다. 

 

여기서 나올 수 있는 state transition은 딱 하나이다. 즉 정답이 우리가 찾고자 하는 aababb라는 답 하나이다.

 

DFA는 답을 유츄하는데 있어 단 하나의 state transition을 수행하면 되기 때문에 Lexical Analysis 내에서 처리속도가 빠르다. 하지만 NFA는 여러개의 possible을 일일히 고려해야 되기 떄문에 처리속도가 느리다. 하지만 DFA에 비해 표현하는 state가 적다. 

그래서 Lexical Analysis는 NFA를 수행해서 전체 Area를 줄인 뒤 DFA를 통해 수행시간을 줄이는 것이 일반적인 처리방식이다.