Finite Automata

oak_cassia·2022년 5월 17일
0

Compiler

목록 보기
2/9

유한 오토마타

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

DFA

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

Extended transition

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

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

NFA

  • Non-Deterministic Finite Automata
  • QQ: A finite set of states
  • \sum: A finite set of input symbols(alphabet)
  • δ\delta: A transition function, a function δ:Q×({ϵ})2Q\delta: Q \times (\sum \cup \{\epsilon\}) \rightarrow 2^Q
  • q0q_0: A start state, q0Qq_0 \in Q
  • FF: A set of final state FQF \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은 인식된 문자의 집합 자체
  • 약간의 에러가 감지될 수 있다.
    • 토큰이 아닌것
profile
벽에 붙은 달팽이 ↑i@

0개의 댓글