Automata Theory오토마타 이론

오토마타 이론(Automata Theory)은 추상 계산 기계의 수학적 모델을 연구하는 이론 컴퓨터 과학의 핵심 분야다. 계산 가능성과 형식 언어의 기초를 이룬다.

오토마타 계층구조

결정론적 유한 오토마타(DFA)

DFA는 5-tuple M = (Q, Σ, δ, q₀, F)로 정의된다.

Q  : 상태 집합
Σ  : 입력 알파벳
δ  : Q × Σ → Q  (전이 함수)
q₀ : 초기 상태
F  : 수락 상태 집합

예: "ab"로 끝나는 문자열을 인식하는 DFA
상태: {s0, s1, s2}
δ(s0, a) = s1
δ(s0, b) = s0
δ(s1, a) = s1
δ(s1, b) = s2  ← 수락 상태
δ(s2, a) = s1
δ(s2, b) = s0

비결정론적 유한 오토마타(NFA)

NFA는 동일 입력에 여러 전이가 가능하며, ε-전이(입력 없이 전이)를 허용한다. DFA와 인식 능력은 동일하지만 표현이 더 간결하다.

서브셋 구성(Subset Construction):
NFA → DFA 변환 알고리즘
NFA 상태 수 n → DFA 최대 2ⁿ 상태

푸시다운 오토마타(PDA)

스택을 추가해 문맥자유 언어를 인식한다.

예: {aⁿbⁿ | n ≥ 1} 인식
1. 'a' 읽을 때마다 스택에 push
2. 'b' 읽을 때마다 스택에서 pop
3. 입력 끝에 스택이 비어있으면 수락

튜링 기계

가장 강력한 계산 모델로, 무한 테이프 위에서 읽기/쓰기/이동이 가능하다. 처치-튜링 명제에 따르면 직관적으로 계산 가능한 모든 함수는 튜링 기계로 계산 가능하다.

관련 개념

• •형식 언어
• •P vs NP 문제
• •복잡도 클래스
• •파서 컴비네이터