Finite Automata

유한 오토마타

• Regular language를 인식하기 위한 오토마타
• 한정된 전이 그래프, 간선에 알파벳이 있다.

DFA

• Deterministic finite automata
• $Q$: A finite set of states
• $\sum$: A finite set of input symbols(alphabet)
• $\delta$: A transition function, a function $\delta: Q \times \sum \rightarrow Q$
• $q_0$: A start state, $q_0 \in Q$
• $F$: A set of final state $F \subseteq Q$
• 위와 같은 5종류 튜플로 구성
• 어떤 상태에서 받은 문자에 따른 function은 고유하게 결정

Extended transition

• $\delta^*:Q \times \sum^* \rightarrow Q$
• $\delta^*(q,w)$: q에서 시작해 w의 문자열을 통해 어떤 상태로 귀결

시작 문자로 시작해서 w(string) 입력을 처리한 뒤 Final state 중 하나에 있다면 w는 인식된 것(언어에 속함)

NFA

• Non-Deterministic Finite Automata
• $Q$: A finite set of states
• $\sum$: A finite set of input symbols(alphabet)
• $\delta$: A transition function, a function $\delta: Q \times (\sum \cup \{\epsilon\}) \rightarrow 2^Q$
• $q_0$: A start state, $q_0 \in Q$
• $F$: A set of final state $F \subseteq Q$
• 델타가 알파벳과 엡실론이 추가되는 것과, Q의 부분집합으로 유도 되는 것만 다르다.

$\epsilon$-closure

• 하나의 state에서 엡실론으로 전이될 수 있는 상태들의 집합

NFA와 DFA의 언어 인식범위는 같다.

• NFA를 DFA로 전환할 수 있다.

---

정규언어로 NFA 만들기

• 먼저
  1. a
  2. $\epsilon$
  3. $\empty$
     를 언어로 가질 수 있다. 어떻게 되는지 생각
• $+$
• concatenate
• $^*$ 의 경우를 생각해 보자

엡실론 NFA를 DFA로 전환

한 state의 엡실론 closure를 하나의 state로 생각해 전이 과정을 정리

• NFA도 엡실론만 없을 뿐 같다.
• 입력에 대해 어느 state로 가는지 찾고 새로운 state를 만들면 된다

DFA 최적화

• 일반 state와 final state로 클래스를 나눈다.
• 입력에 대해 어떤 클래스로 가는지 정리하고 공통된 state 끼리 클래스로 묶는다.
• 변화가 없을 때 까지 반복

위 과정으로 정규 언어를 DFA로 만들 수 있다. 왜 만들까? 어휘 분석이 가능하다.

어휘분석

Lexical analysis

• 소스 코드를 읽어 토큰으로 나눈다.
• 토큰은 하나의 의미를 가진 단위
• lexeme은 인식된 문자의 집합 자체
• 약간의 에러가 감지될 수 있다.
  • 토큰이 아닌것