유한 오토마타 (finite automaton)
쉽게 풀면
유한 오토마타는 정해진 몇 개의 '상태' 사이를 입력 문자에 따라 이동하는 아주 단순한 기계다. 예를 들어 '짝수 개의 0을 포함하는 문자열인지 판별하는' 오토마타는 '짝수 상태'와 '홀수 상태' 단 두 개의 상태만으로 만들 수 있다.
메모리(테이프)를 가진 튜링 기계와 달리 오토마타는 이전에 무엇을 봤는지에 대한 정보를 오직 현재 상태로만 기억할 수 있어 표현력이 제한적이지만, 그만큼 매우 빠르고 예측 가능하게 동작한다. 정규 표현식이 인식하는 언어가 바로 유한 오토마타로 인식 가능한 언어와 같다.
왜 중요한가
유한 오토마타는 계산이론의 가장 기초적인 모델이면서도, 컴파일러의 어휘 분석기, 네트워크 프로토콜 검증, 정규 표현식 엔진 등 실제 시스템 구현에 직접 쓰이는 실용적인 도구입니다.
상태 수가 유한하다는 단순한 구조 덕분에 시스템이 특정 오류 상태에 빠지지 않음을 수학적으로 증명하기 쉬워, 형식 검증이나 모델 체킹 연구에서 기본 표현 수단으로 자주 등장합니다. 또한 정규 언어라는 개념을 통해 촘스키 위계의 다른 계산 모델들과 표현력을 비교하는 이론적 논의의 출발점이 되기도 합니다.
핵심 정리
- 유한 오토마타는 (상태 집합 Q, 입력 기호 Σ, 전이 함수 δ, 시작 상태 q0, 수락 상태 집합 F) 다섯 가지로 정의되는 계산 모델입니다. 입력 문자열을 한 글자씩 읽으며 상태를 옮기다가 마지막에 수락 상태에 있으면 그 문자열을 받아들입니다.
- 결정적(DFA)은 상태와 입력마다 다음 상태가 하나로 정해지고, 비결정적(NFA)은 여러 갈래가 가능합니다. 두 모델이 인식하는 언어의 범위는 같습니다. NFA를 DFA로 바꾸면 상태 수가 최악의 경우 지수적으로 늘어날 수 있습니다.
- 유한 오토마타가 인식하는 언어가 정규 언어이고, 정규 언어는 정규표현식으로 쓸 수 있는 언어와 같습니다(Kleene, 1956; Rabin & Scott, 1959).
- 기억은 현재 상태뿐이라서, 0과 1의 개수를 맞춰 세는 것처럼 무한한 기억이 필요한 언어(예: 0n1n)는 인식하지 못합니다. 이런 언어는 스택이 있는 푸시다운 오토마타나 튜링 기계가 필요합니다.
예시로 보기
“0이 짝수 개인 문자열만 받아들이는” DFA는 상태가 두 개(짝수 E, 홀수 O)뿐입니다. 시작 상태는 E이고, 0을 읽을 때마다 E와 O를 오가며, 1은 상태를 바꾸지 않습니다. E가 수락 상태입니다. 몇 개의 문자열을 실제로 돌려 본 결과입니다(코드로 계산).
| 입력 | 0의 개수 | 끝난 상태 |
|---|---|---|
(빈 문자열) | 0 | 짝수 상태(수락) |
1 | 0 | 짝수 상태(수락) |
0 | 1 | 홀수 상태(거부) |
01010 | 3 | 홀수 상태(거부) |
1001 | 2 | 짝수 상태(수락) |
000 | 3 | 홀수 상태(거부) |
11111 | 0 | 짝수 상태(수락) |
입력이 아무리 길어도 필요한 기억은 “지금까지 0이 짝수였나 홀수였나”라는 한 비트뿐입니다. 상태 수가 유한한 모델이 할 수 있는 일의 전형입니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 비결정적(NFA)이 더 강력하다. | 인식할 수 있는 언어의 범위는 DFA와 같습니다. 달라지는 것은 표현의 간결함(상태 수)입니다. |
| 유한 오토마타는 이론 속 장난감이다. | 컴파일러의 어휘 분석기, 문자열 검색, 프로토콜 상태 검증 등에 쓰입니다. 다만 실무의 정규표현식 엔진은 역참조처럼 정규 언어를 넘어서는 기능을 확장해 넣은 경우가 있습니다. |
| 유한 오토마타와 유한상태기계는 완전히 같다. | 서로 가깝지만 오토마타 이론에서는 ‘수락/거부’ 판정이 중심이고, 공학에서 말하는 유한상태기계는 출력(밀리·무어 기계)이나 제어 동작을 포함하는 경우가 많습니다(유한상태기계). |
| 상태 수만 늘리면 어떤 언어든 인식한다. | 상태 수가 고정된 유한 오토마타는 입력 길이에 비례해 늘어나는 기억이 필요한 언어를 인식하지 못합니다. 펌핑 보조정리로 이를 증명합니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
상태 기반 시스템(프로토콜, 어휘 분석기 등)을 수학적으로 명확히 모델링할 때 쓰인다.
보안 분야에서는 정상 동작 패턴을 유한 오토마타로 표현하고, 이를 벗어나는 입력을 탐지하는 방식으로 이 모델이 활용됩니다.
컴파일러 이론에서는 소스 코드를 토큰 단위로 나누는 어휘 분석기를 유한 오토마타로 구현해 처리 속도와 정확성을 함께 확보하는 방식이 표준적으로 쓰입니다.
조금 더 깊게 보면
유한 오토마타는 하나의 입력에 대해 다음 상태가 하나로 정해지는 결정적 유한 오토마타(DFA)와, 여러 상태로 동시에 전이할 수 있는 비결정적 유한 오토마타(NFA)로 나뉘는데, 이 둘은 표현력은 동일하지만 NFA가 DFA보다 상태 수를 훨씬 적게 사용해 더 간결하게 표현할 수 있다는 점이 자주 논의됩니다. 또한 임의 개수를 세는 작업처럼 오토마타로 표현할 수 없는 언어가 존재함을 보이는 펌핑 렘마(pumping lemma) 같은 증명 기법도 이 모델의 한계를 이해하는 데 함께 다뤄집니다.
주의할 점
유한 오토마타는 상태 수가 유한하다는 제약 때문에 임의 개수를 세는 것과 같은 무제한 메모리가 필요한 작업은 표현할 수 없다.
헷갈리기 쉬운 용어
계산 모델은 기억 장치의 차이로 능력이 갈립니다.
| 모델 | 기억 장치 | 인식하는 언어 | 예 |
|---|---|---|---|
| 유한 오토마타 | 현재 상태뿐 | 정규 언어 | 짝수 개의 0, 특정 패턴 검색 |
| 푸시다운 오토마타 | 스택 하나 | 문맥자유 언어 | 괄호가 올바르게 짝지어진 문자열 |
| 튜링 기계 | 무한한 테이프 | 재귀적 열거 가능 언어 | 일반적인 알고리즘 계산 |
| 정규표현식 | (모델이 아니라 표기법) | 정규 언어(기본 연산 기준) | (ab)* 꼴의 패턴 |
참고 문헌
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
- Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
- Rabin, M. O., & Scott, D. (1959). Finite automata and their decision problems. IBM Journal of Research and Development, 3(2), 114–125.
- Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In C. E. Shannon & J. McCarthy (Eds.), Automata Studies (pp. 3–41). Princeton University Press.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.