유한 오토마타
IT 위키
(유한 상태 기계에서 넘어옴)
Finite Automata; FA; 유한 상태 기계
입력을 한 글자씩 읽으며 유한한 개수의 상태 사이를 옮겨 다니는 계산 모형
기억 장치가 상태 하나뿐이라 가장 단순한 계산 모형이며, 정규 언어를 인식한다. 어휘 분석기, 프로토콜 처리, 문자열 검색 등에 쓰인다.
5-튜플 (Q, Σ, δ, q0, F) 로 정의한다.
- Q : 상태의 유한 집합
- Σ : 입력 알파벳
- δ : 전이 함수
- q0 : 시작 상태
- F : 종료(수락) 상태의 집합
| DFA | NFA | |
|---|---|---|
| 이름 | 결정적 유한 오토마타 | 비결정적 유한 오토마타 |
| 전이 함수 | δ : Q × Σ → Q | δ : Q × (Σ ∪ {ε}) → 2Q |
| 다음 상태 | 하나로 정해진다 | 여러 개 중에서 선택할 수 있다 |
| ε-전이 | 없다 | 입력을 읽지 않고도 상태를 옮길 수 있다 |
| 상태 수 | 많아질 수 있다 | 적다 |
| 구현 | 표로 바로 옮겨 빠르다 | 모의 실행이 필요하다 |
두 모형의 인식 능력은 같다. 어떤 NFA도 부분집합 구성법(subset construction)으로 같은 언어를 인식하는 DFA로 변환할 수 있다. 상태 수가 최대 2n개로 늘어날 뿐이다.
유한 오토마타가 인식하는 것은 정규 언어까지다. `a`n`b`n 처럼 개수를 세어 맞춰야 하는 언어나 괄호의 짝을 맞추는 언어는 기억할 수 있는 상태가 유한하기 때문에 인식하지 못한다. 문맥 자유 언어를 인식하려면 스택을 붙인 푸시다운 오토마타가 필요하다. 시험에서 "유한 오토마타가 모든 문맥 자유 언어를 인식한다"는 보기는 틀린 서술로 자주 나온다.
| 유형 | 언어 | 인식하는 기계 |
|---|---|---|
| 유형 3 | 정규 언어 | 유한 오토마타 |
| 유형 2 | 문맥 자유 언어 | 푸시다운 오토마타 |
| 유형 1 | 문맥 의존 언어 | 선형 구속 오토마타 |
| 유형 0 | 귀납적 열거 가능 언어 | 튜링 기계 |
