유한 상태 기계(finite state machine, FSM)는 이론 컴퓨터 과학 및 전자 공학에서 계산 모델의 일종으로, 유한한 수의 상태를 가지며 입력 신호에 따라 상태 간 전이를 수행하는 시스템이다. 유한 상태 기계는 현재 상태와 입력에 따라 다음 상태와 출력을 결정하며, 일반적으로 상태 다이어그램이나 상태 전이표로 표현된다.
이 모델은 두 가지 주요 형태로 나뉜다. 하나는 무출력형인 '무어 기계(Moore machine)', 다른 하나는 입력과 상태에 따라 출력이 결정되는 '마이너드 기계(Mealy machine)'이다. 두 형태 모두 계산 이론에서 정규 언어를 인식하는 능력을 가지며, 정규 표현식과 동등한 표현력을 지닌다.
유한 상태 기계는 소프트웨어 엔지니어링, 하드웨어 설계, 통신 프로토콜, 문법 분석기 구현 등 다양한 분야에 응용된다. 예를 들어, 간단한 제어 시스템(자동 문, 엘리베이터 제어), 렉시컬 분석기, 네트워크 프로토콜 상태 관리 등에 활용된다.
이론적으로는 유한 상태 기계는 튜링 기계보다 계산 능력이 제한적이며, 무한한 메모리를 갖지 못하므로 반복적 패턴이나 중첩 구조(예: 괄호의 중첩)를 인식할 수 없다. 이는 계층적으로는 정규 언어 수준에 해당하며, 추상적인 계산 모델로서 형식 언어 이론에서 중요한 위치를 차지한다.
유한 상태 기계는 20세기 중반, 클로드 섀넌과 워런 맥컬록 등이 제안한 개념을 기반으로 발전하였으며, 이후 존 폰 노이만과 스蒂븐 커클랜드 등의 연구를 통해 형식화되었다.