유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA; 복수형: 유한 오토마타)은 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데 쓰이는 수학적 모델이다. 간단히 '상태 기계'라고 부르기도 한다.
정의
유한 상태 기계는 유한한 개수의 상태(state)를 가질 수 있는 오토마타, 즉 추상 기계이다. 이러한 기계는 한 번에 오로지 하나의 상태만을 가지며, 현재 상태(Current State)란 임의의 주어진 시간의 상태를 칭한다. 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)라고 한다. 특정한 유한 오토마톤은 현재 상태로부터 가능한 전이 상태와, 이러한 전이를 유발하는 조건들의 집합으로서 정의된다.
분류
유한 상태 기계는 크게 두 가지 유형으로 나뉜다.
수리 기계(Acceptors)와 인식기(Recognizers)는 입력값이 기계에서 받아들여졌는지 이진값인 '예 또는 아니오'로 결과를 출력한다. 모든 입력이 처리되었을 때, 현재 상태가 받아들여질 수 있는 상태(accept state)라면 입력값은 기계에 의해 받아들여진 것이고, 그렇지 않으면 거부된 것이다. 유한 오토마타가 받아들일 수 있는 모든 언어는 정규 표현식(regular expression)이며, 그 역도 성립한다.
변환기(Transducers)는 상태와 주어진 입력값에 기반하여 출력값을 생성한다. 변환기에는 두 가지 주요 모델이 있다.
-
무어 모델(Moore model): 출력값이 오직 현재 상태에만 의존하여 결정된다. 수학적으로 (S, S₀, Σ, Λ, T, G)의 6-튜플로 정의되며, 여기서 S는 상태의 유한 집합, S₀는 초기 상태, Σ는 입력값의 유한 집합, Λ는 출력값의 유한 집합, T는 상태 전이 함수(S × Σ → S), G는 현재 상태 기반 출력 함수(S → Λ)이다.
-
밀리 모델(Mealy model): 출력값이 현재 상태와 현재 입력값 모두에 의존하여 결정된다. 수학적으로 (S, S₀, Σ, Λ, T, G)의 6-튜플로 정의되며, G는 현재 상태와 입력값을 기반으로 출력값을 반환하는 함수(S × Σ → Λ)이다.
결정적 유한 오토마타와 비결정적 유한 오토마타
결정적 유한 오토마타(Deterministic Finite Automata, DFA)는 (Q, Σ, s₀, δ, F)의 5-튜플로 구성된다. Q는 상태의 공집합이 아닌 유한 집합, Σ는 입력 문자(유한하며 비어 있지 않은 기호의 집합), δ는 상태 전이 함수(Q × Σ → Q), s₀는 초기 상태(Q의 원소), F는 최종 상태의 집합(Q의 원소)이다. DFA에서 모든 상태는 각각의 가능한 입력에 대해 정확히 하나의 변환된 상태를 가진다.
비결정적 유한 오토마타(Nondeterministic Finite Automata, NFA)는 (Q, Σ, s₀, δ, F)의 5-튜플로 구성되나, 상태 전이 함수가 δ: Q × (Σ ∪ {ε}) → P(Q)로 정의되어, 하나의 입력에 대해 여러 개의 다음 상태가 존재할 수 있고 ε-전이(입력 없이 상태 전이)가 가능하다. 모든 NFA는 멱집합 구성(Powerset Construction) 알고리즘을 통해 동일한 기능을 가지는 DFA로 변환될 수 있다.
역사
유한 상태 기계의 개념은 디지털 컴퓨터에 대한 추상적 모델로서 19세기 중반부터 다양한 분야의 과학자들에 의해 연구되었다. 고대와 중세 시기에는 자동기계(Automata)의 형태로 존재하였으며, 알렉산드리아의 헤론, 크테시비우스, 알 자자리, 장영실 등이 자동기계를 제작한 기록이 남아 있다.
현대적 의미의 유한 상태 기계는 20세기에 들어 본격적으로 발전하였다. 앨런 튜링(Alan Turing)은 1936년 튜링 기계(Turing Machine)의 개념을 소개하였으며, 워런 맥컬럭(Warren McCulloch)과 월터 피츠(Walter Pitts)는 1943년 신경 네트워크 이론과 오토마타 이론에 기여하였다. 조지 H. 밀리(George H. Mealy)는 1955년 밀리 기계를, 에드워드 F. 무어(Edward F. Moore)는 1956년 무어 기계의 개념을 각각 발표하였다. 노엄 촘스키(Noam Chomsky)는 1956년 촘스키 위계(Chomsky hierarchy)를 통해 정규 언어가 유한 오토마타로 인식 가능함을 보였다.
표현 방법
유한 상태 기계는 상태 전이 표(state transition table), UML 상태 기계 다이어그램, SDL 상태 기계 등 다양한 방식으로 표현될 수 있다.
응용 분야
유한 상태 기계는 하드웨어와 소프트웨어 양쪽에서 폭넓게 사용된다. 하드웨어적으로는 디지털 회로, 설계 가능 논리 소자, 프로그래머블 로직 컨트롤러, 플립플롭 등에 활용된다. 소프트웨어적으로는 응용 프로그램 설계, 텍스트 필터링(정규 표현식), 컴파일러의 어휘 분석기(lexical analyzer) 설계, 패리티 비트 생성, 통신 프로토콜, 게임 인공지능, 임베디드 시스템 제어 등 다양한 분야에서 사용된다.
