요약
- 유한 오토마타(FA)는 유한한 개수의 상태만 가질 수 있어, 현재 상태 외에 추가 정보를 기억할 수 없다
- 튜링 머신의 무한 테이프를 제거한 현실적인 계산 모델
본문
핵심 특성
- 유한한 상태: 상태의 개수가 유한함
- 현재 상태만 기억: 과거 경로나 히스토리를 저장하지 않음
- 결정적 전이: 현재 상태 + 입력 → 다음 상태가 결정됨
5-튜플 구성 요소
- Q: 유한한 상태 집합
- Σ (시그마): 입력 알파벳 집합
- δ (델타): 전이 함수 (Q × Σ → Q)
- q₀: 시작 상태
- F: 수락 상태 집합
튜링 머신과의 비교
튜링 머신은 무한한 테이프(메모리)를 가진 이론적 모델이다. 유한 오토마타는 이를 단순화하여:
- 무한 테이프 → 없음 (상태만 존재)
- 읽기/쓰기 → 읽기만
- 양방향 이동 → 단방향 (왼쪽→오른쪽)
한계: 무한한 상태가 필요한 문제
괄호 짝 맞추기 ((()))는 유한 오토마타로 불가능하다.
- 열린 괄호의 개수를 세어야 함
(,((,(((, ... 각각을 구분하려면 무한한 상태가 필요- 이런 문제는 스택을 가진 **푸시다운 오토마타(PDA)**가 필요
실용적 활용
- 정규 표현식 엔진 (정규 표현식 ↔ FA는 수학적으로 동치)
- 어휘 분석기 (lexer)
- 프로토콜 상태 관리
- 게임 AI 상태 머신