유한 오토마타와 DFA·NFA의 상태 전이 모델
유한 오토마타의 구성과 DFA·NFA 차이, 정규 표현식 변환, 상태 최소화와 컴파일러·프로토콜 활용을 정리한다.
2026-08-14 · 최초 발행 2026-01-02
입력을 읽으며 상태를 바꾸는 계산 모델
유한 오토마타(Finite Automata, FA)는 유한한 수의 상태를 두고, 입력 기호에 따라 상태를 옮겨 가며 문자열을 인식하는 추상 계산 모델이다. 형식 언어 이론과 컴파일러 설계의 기반이며, 정규 표현식과 같은 표현력을 가진다.
형식적으로는 다음 5-튜플로 표현한다.
(Q, Σ, δ, q₀, F)
- Q: 유한한 상태 집합
- Σ: 입력 알파벳, 즉 유한한 기호 집합
- δ: 전이 함수(Q × Σ → Q 또는 Q × Σ → 2^Q)
- q₀: 초기 상태(q₀ ∈ Q)
- F: 최종 상태 집합(F ⊆ Q)
처리는 초기 상태 q₀에서 시작한다. 입력 문자열을 왼쪽에서 오른쪽으로 읽고, 각 기호에 대응하는 전이를 적용한다. 문자열을 모두 읽은 뒤 최종 상태 F에 있으면 수락하며, 그렇지 않거나 전이가 불가능하면 거부한다.
상태 수와 상태로 표현되는 메모리는 유한하다. 실행 중 무한 루프는 가능하지만, 새로운 상태를 끝없이 만들 수는 없다. 다음 상태가 하나로 정해지는 모델은 DFA이고, 여러 경로가 가능할 수 있는 모델은 NFA다.
하나의 경로만 따르는 DFA
DFA(Deterministic Finite Automaton)는 현재 상태와 입력이 주어졌을 때 다음 상태가 정확히 하나로 결정된다. 전이 함수는 δ: Q × Σ → Q이며, 처리 과정에 모호한 선택지가 없다.
짝수 개의 a를 포함하는 문자열을 인식하는 DFA는 다음과 같이 정의할 수 있다.
Q = {even, odd}
Σ = {a, b}
q₀ = even
F = {even}
전이 함수 δ:
δ(even, a) = odd
δ(even, b) = even
δ(odd, a) = even
δ(odd, b) = odd
전이 규칙은 표로도 확인할 수 있다.
| 현재 상태 | 입력 'a' | 입력 'b' |
|---|---|---|
| even | odd | even |
| odd | even | odd |
문자열 "aabaa"를 실행하면 상태는 even에서 시작해 odd, even, even, odd, even 순으로 바뀐다. 마지막 상태가 최종 상태이므로 이 문자열은 수락된다.
여러 상태 가능성을 함께 다루는 NFA
NFA(Non-deterministic Finite Automaton)는 한 상태에서 같은 입력을 읽더라도 0개 이상의 다음 상태로 전이할 수 있다. 전이 함수는 δ: Q × Σ → 2^Q로 표현한다. 입력을 소비하지 않는 ε-전이도 허용한다.
여러 경로를 이론적으로 탐색했을 때 수락 상태에 도달하는 경로가 하나라도 있으면 문자열을 수락한다. NFA는 DFA로 변환할 수 있으므로 두 모델의 표현력은 같다.
ε-NFA에서는 입력 기호 없이 상태가 전이된다. 이때 전이 함수는 δ: Q × (Σ ∪ {ε}) → 2^Q가 되며, 정규 표현식을 구성할 때 각 조각을 연결하는 데 활용된다.
(a|b)*abb 패턴을 인식하는 예시는 다음과 같다.
정규 표현식과 상태 머신의 변환
정규 표현식, NFA, DFA는 모두 정규 언어를 표현한다. 따라서 서로 변환할 수 있다. 정규 표현식을 NFA로 옮길 때는 Thompson's Construction을 사용하며, 각 연산자(*, |, •)를 NFA 조각으로 만든 뒤 ε-전이로 연결한다.
NFA를 DFA로 만들 때는 부분집합 구성법을 쓴다.
- NFA 상태의 부분집합을 DFA 상태로 매핑한다.
- ε-전이로 도달할 수 있는 모든 상태인 ε-closure를 계산한다.
- 부분집합 사이의 전이 함수를 구성한다.
- NFA의 최종 상태를 포함한 부분집합을 DFA의 최종 상태로 둔다.
이 변환에서는 상태 수가 2^n까지 증가할 수 있다. 실제 구성에서는 도달 가능한 상태만 생성한다. 결정성을 얻는 대신 효율성이 감소할 수 있다는 점을 고려해야 한다.
상태 전이가 실제 시스템에 쓰이는 자리
컴파일러의 어휘 분석기는 키워드, 식별자, 연산자를 토큰으로 구분한다. DFA 기반 스캐너 생성과 Lex, Flex 도구가 이 영역에 속한다. grep, sed, awk의 패턴 매칭과 정규 표현식 엔진도 같은 모델을 이용해 텍스트 검색과 치환을 수행한다.
네트워크에서는 프로토콜 상태 머신으로 연결과 요청을 다룬다. TCP 연결 상태인 LISTEN, SYN_SENT, ESTABLISHED, CLOSE_WAIT, HTTP 요청 파싱, 패킷 필터링과 방화벽 처리가 대표적이다.
문자열 검색에서는 KMP(Knuth-Morris-Pratt) 알고리즘의 실패 함수를 DFA로 표현해 패턴 매칭을 최적화할 수 있다. Aho-Corasick 알고리즘은 다중 패턴을 동시에 검색하며, 백신 소프트웨어의 시그니처 매칭에 사용된다.
하드웨어 제어 로직도 유한 상태 기계(FSM)로 설계한다. 시퀀스 검출기와 프로토콜 컨트롤러는 상태 레지스터와 조합 논리 회로로 전이 함수를 구현하며, Verilog/VHDL 구현이 이 방식을 따른다.
상태만으로 처리할 수 없는 문제
유한 오토마타는 {a^n b^n | n ≥ 0}처럼 a와 b의 개수가 같은 언어를 인식하지 못한다. 괄호 균형 검사도 같은 범주에 속하며, 이런 문제에는 문맥 자유 문법(Context-Free Grammar)이 필요하다. Pumping Lemma는 특정 언어가 정규 언어가 아님을 보일 때 쓰는 필요조건으로, 반복 가능한 부분 문자열의 존재를 다룬다.
상태만으로 기억을 표현하므로 무한 메모리가 필요한 카운터, 스택 또는 큐가 필요한 작업은 처리할 수 없다. 이 경우 Pushdown Automaton(PDA) 같은 모델로 확장해야 한다. NFA를 DFA로 변환할 때의 상태 폭발(State Explosion)처럼 상태 수가 지수적으로 증가할 수 있다는 점도 복잡한 패턴 인식에서 제약이 된다.
동등한 상태를 합치는 DFA 최소화
DFA 최소화의 목표는 같은 언어를 인식하면서 상태 수가 가장 적은 DFA를 만드는 것이다. 중복 상태를 제거해 효율성을 높일 수 있다.
Myhill-Nerode 정리는 구별할 수 없는 상태를 병합하는 근거가 되며, 최소 DFA가 유일함을 설명한다. Hopcroft's Algorithm은 최종 상태와 비최종 상태를 먼저 그룹으로 나눈 뒤, 각 입력에서 서로 다른 그룹으로 전이되는 상태를 분리한다. 더 이상 분리할 수 없을 때 각 그룹을 하나의 상태로 병합한다.
유한 오토마타는 정규 언어 범위에서 간결하고 구현하기 쉬운 상태 전이 모델이다. DFA와 NFA의 차이, 정규 표현식과의 변환, 최소화 과정은 컴파일러·네트워크·문자열 검색·하드웨어 설계에서 상태 기반 처리를 설계하고 검토하는 공통 기반이 된다.