Finite Automata

 

Automata

 

일반적인 Automata의 개념

Automata를 분류하는데 2가지 방법이 있다.

 

1. 현재 state에서 다음 state의 갯수에 따른 분류

 - Deterministic automata : 하나의 입력을 받았을 때 다음 state는 유일

 - Non-deterministic automata : 하나의 입력을 받았을 때 다음 state가 2개 이상

 

2. 기능적인 측면에서의 분류

- 인식기(accepter) : 입력된 결과에 대해 accept/reject 등을 표시

- 변환기(transducer) : 주어진 입력에 대응하는 새로운 문자열 출력

---

Finite Automata

어떤 알파벳 ∑로 부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템에서 변화할 수 있는 상태가 유한개인 것. 컴파일러의 Scanner(어휘 분석기)는 대표적인 Finite automaton이다.

 

표현 방법

informal : 상태전이도(state transition diagram)와 같이 그래프를 사용할 수 있음

Formal : 5가지의 구성 원소들로 표현하는 방법

---

Formal definition of Finite Automata

외워두도록 하자

너무 많다... 다른 표현 방식을 쓰도록 하자

위에 있는 Formal definition을 나타낸 state transition table

---

DFA와 NFA

state transition table을 보면 대응하는 state가 1개 밖에 없다

---

NFA

---

NFA -> DFA

• DFA보다 NFA가 언어의 구조를 쉽게 표현한다
• NFA는 DFA 보다 프로그램으로 구현하기 어려움
• DFA는 NFA 보다 프로그램으로 구현했을 경우에 효율면에서 훨씬 우수
• 이러한 특징들로 인해 서로 변환이 필요

NFA를 DFA로 변환

• 𝜀-전이가 있는 NFA를 DFA로 변환
• 𝜀-전이가 없는 NFA를 DFA로 변환

𝜀-transition이 있는 NFA를 DFA로 변환

• 𝜀-closure를 이용하여 변환
• NFA에서 의미가 같은 여러 state들이 DFA에서 하나의 state로 변한된다는 것

---