[컴파일러] 2.4. 유한 오토마타

유한 오토마타란 어휘분석기로 바꾸는 방법을 고찰한 형식론으로 단순히 각 입력에 대해 "yes" or "no"로 대답한다.

유한 오토마타는 다음 다섯 가지의 요소로 구성된다.

 

1. 상태(State)

오토마타가 가질 수 있는 상태 집합

 

2. 입력 알파벳(Input Alphabet)

입력 문자의 집합으로 빈 스트링은 제외한다.

 

3. 전이함수(Transition Function)

상태 및 입력에 대한 다음 상태를 결정

 

4. 초기 상태(Initial State) 또는 시작 상태(Start State)

오토마타가 시작하는 상태로 하나여야 한다.

 

5. 수락 상태(Accepting State) 또는 종료 상태(Final State)

입력 문자열을 수락하는 상태의 집합

 

 

또한 전이도와 매우 유사한데, 유한 오토마타는 추상적인 수학적 개념이고 전이도는 시각적 도표라고 생각하면 된다.

 

---

유한 오토마타는 2가지 종류가 있다.

 

1. 비결정 유한 오토마타(NFA: Nondeterministic Finite Automata)

간선의 라벨에 대한 정의가 없다. 즉 어떠한 입력을 받았을 때 여러 상태로 이동할 수 있다.

 

2. 결정 유한 오토마타(DFA: Deterministic Finite Automata)

각 상태와 입력 알파벳에 대해 간선은 정확히 한 개다.

 

아래는 NFA와 DFA에 대하여 정규식 (a|b)*abb를 인식하는 전이도 예시이다.

 

 

뭐가 다른가 싶기도 하지만 차이점은 0인 상태에서 a를 입력받았을 때이다.

비결정 유한 오토마타(NFA)는 0인 상태에서 a를 입력받았을 때 0으로도, 1로도 갈 수 있지만

결정 유한 오토마타(DFA)는 0인 상태에서 a를 입력받았을 때 오직 1로만 갈 수 있다.

 

---

여기서 만약 "abababb"라는 입력값이 들어왔을 때는 앞선 전이표에서 가능하기 때문에 yes를 출력한다.

반면에 "bbababa"라는 입력값이 들어왔을 때는 앞선 전이표에 불가능한 패턴이기 때문에 no를 출력한다.