유한 오토마타

Finite Automata; FA; 유한 상태 기계

입력을 한 글자씩 읽으며 유한한 개수의 상태 사이를 옮겨 다니는 계산 모형

기억 장치가 상태 하나뿐이라 가장 단순한 계산 모형이며, 정규 언어를 인식한다. 어휘 분석기, 프로토콜 처리, 문자열 검색 등에 쓰인다.

구성

5-튜플 (Q, Σ, δ, q0, F) 로 정의한다.

Q : 상태의 유한 집합
Σ : 입력 알파벳
δ : 전이 함수
q0 : 시작 상태
F : 종료(수락) 상태의 집합

DFA 와 NFA

	DFA	NFA
이름	결정적 유한 오토마타	비결정적 유한 오토마타
전이 함수	δ : Q × Σ → Q	δ : Q × (Σ ∪ {ε}) → 2^Q
다음 상태	하나로 정해진다	여러 개 중에서 선택할 수 있다
ε-전이	없다	입력을 읽지 않고도 상태를 옮길 수 있다
상태 수	많아질 수 있다	적다
구현	표로 바로 옮겨 빠르다	모의 실행이 필요하다

두 모형의 인식 능력은 같다. 어떤 NFA도 부분집합 구성법(subset construction)으로 같은 언어를 인식하는 DFA로 변환할 수 있다. 상태 수가 최대 2ⁿ개로 늘어날 뿐이다.

한계

유한 오토마타가 인식하는 것은 정규 언어까지다. `a`ⁿ`b`ⁿ 처럼 개수를 세어 맞춰야 하는 언어나 괄호의 짝을 맞추는 언어는 기억할 수 있는 상태가 유한하기 때문에 인식하지 못한다. 문맥 자유 언어를 인식하려면 스택을 붙인 푸시다운 오토마타가 필요하다. 시험에서 "유한 오토마타가 모든 문맥 자유 언어를 인식한다"는 보기는 틀린 서술로 자주 나온다.

촘스키 계층과의 대응

유형	언어	인식하는 기계
유형 3	정규 언어	유한 오토마타
유형 2	문맥 자유 언어	푸시다운 오토마타
유형 1	문맥 의존 언어	선형 구속 오토마타
유형 0	귀납적 열거 가능 언어	튜링 기계

같이 보기