형식언어와 오토마타 ( formal language and automata )

목표
- 형식언어의 문법 및 표기법 이해
- 정규언어와 유한 오토마타의 관계
- 정규표현, 정규문법, 유한 오토마타가 서로 변환되는 관계

요약
- 형식언어 : 어떤 알파벳에서 얻은 기호들로 구성되는 문자열들의 집합

- 형식문법 : 형식언어를 생성하기 위한 규칙.
    정규표현(regular expression)
    문법도표(syntax diagram)
    BNF(Backus-Naur Form)
    EBNF(Extended BNF)

- 유한 오토마타 : 형식언어 인식을 위한 방법
    결정적 유한 오토마타(Deterministic Finite Automata,DFA) = 하나의 입력문자열에 대해서 오직 하나의 다음 상태가 결정됨
    비결정적 유한 오토마타(Nondeterministic Finite Automata,NFA) = 다음 상태가 둘 이상 존재하는 경우

- DFA, NFA 비교 (서로 변환 가능함)
    DFA : 프로그램 구현 효율이 좋다. 일반적인 구현에 적합
    NFA : 언어 구조 표현이 쉽지만 프로그램 구현이 힘들다. 언어구조 표현에 적합

- 정규문법, 정규표현, 유한 오토마타는 서로 동치관계에 있으며 변환 가능

DFA와 NFA의 동치관계
- DFA의 상태들은 NFA의 모든 상태들의 부분집합이므로 증명하지 않아도 자명함
- ε-전이가 있는 NFA를 DFA로 변환/ε-전이가 없는 NFA를 DFA로 변환함으로써 증명

DFA의 상태 수 최소화(state minimization)
- 목적 : 기억공간 최소화로 인한 프로그램 간소화 효과
- 방법 : 동치 관계(equivalence relation)를 이용하여 상태 수를 합침(state merge)

동치관계(equivalence relation)
- 정규문법=>정규표현
- 정규표현=>유한 오토마타
- 유한 오토마타=>정규문법

관련 프로그램
LEX
PCLEX