유한 오토마타 (finite automaton)
쉽게 풀면
유한 오토마타는 정해진 몇 개의 '상태' 사이를 입력 문자에 따라 이동하는 아주 단순한 기계다. 예를 들어 '짝수 개의 0을 포함하는 문자열인지 판별하는' 오토마타는 '짝수 상태'와 '홀수 상태' 단 두 개의 상태만으로 만들 수 있다. 메모리(테이프)를 가진 튜링 기계와 달리 오토마타는 이전에 무엇을 봤는지에 대한 정보를 오직 현재 상태로만 기억할 수 있어 표현력이 제한적이지만, 그만큼 매우 빠르고 예측 가능하게 동작한다. 정규 표현식이 인식하는 언어가 바로 유한 오토마타로 인식 가능한 언어와 같다.
왜 중요한가
유한 오토마타는 계산이론의 가장 기초적인 모델이면서도, 컴파일러의 어휘 분석기, 네트워크 프로토콜 검증, 정규 표현식 엔진 등 실제 시스템 구현에 직접 쓰이는 실용적인 도구입니다. 상태 수가 유한하다는 단순한 구조 덕분에 시스템이 특정 오류 상태에 빠지지 않음을 수학적으로 증명하기 쉬워, 형식 검증이나 모델 체킹 연구에서 기본 표현 수단으로 자주 등장합니다. 또한 정규 언어라는 개념을 통해 촘스키 위계의 다른 계산 모델들과 표현력을 비교하는 이론적 논의의 출발점이 되기도 합니다.
논문에서는 이렇게 쓰입니다
상태 기반 시스템(프로토콜, 어휘 분석기 등)을 수학적으로 명확히 모델링할 때 쓰인다.
보안 분야에서는 정상 동작 패턴을 유한 오토마타로 표현하고, 이를 벗어나는 입력을 탐지하는 방식으로 이 모델이 활용됩니다.
컴파일러 이론에서는 소스 코드를 토큰 단위로 나누는 어휘 분석기를 유한 오토마타로 구현해 처리 속도와 정확성을 함께 확보하는 방식이 표준적으로 쓰입니다.
조금 더 깊게 보면
유한 오토마타는 하나의 입력에 대해 다음 상태가 하나로 정해지는 결정적 유한 오토마타(DFA)와, 여러 상태로 동시에 전이할 수 있는 비결정적 유한 오토마타(NFA)로 나뉘는데, 이 둘은 표현력은 동일하지만 NFA가 DFA보다 상태 수를 훨씬 적게 사용해 더 간결하게 표현할 수 있다는 점이 자주 논의됩니다. 또한 임의 개수를 세는 작업처럼 오토마타로 표현할 수 없는 언어가 존재함을 보이는 펌핑 렘마(pumping lemma) 같은 증명 기법도 이 모델의 한계를 이해하는 데 함께 다뤄집니다.
주의할 점
유한 오토마타는 상태 수가 유한하다는 제약 때문에 임의 개수를 세는 것과 같은 무제한 메모리가 필요한 작업은 표현할 수 없다.