유한상태기계 (Finite State Machine)

한 줄 정의: 시스템이 가질 수 있는 상태들과, 어떤 입력이 들어왔을 때 한 상태에서 다른 상태로 어떻게 옮겨가는지를 정리한 모델입니다.

쉽게 풀면

신호등을 떠올려 보세요. 신호등은 "빨강", "노랑", "초록"이라는 정해진 상태만 가질 수 있고, 일정 시간이 지나면 정해진 순서대로만 상태가 바뀝니다(빨강 → 초록 → 노랑 → 빨강). 갑자기 빨강에서 노랑을 건너뛰고 초록으로 바뀌는 일은 없습니다. 유한상태기계는 이렇게 "가질 수 있는 상태가 정해져 있고, 상태 사이를 옮겨가는 규칙(전이)도 정해져 있는" 시스템을 표현하는 방법입니다. 자판기, 엘리베이터, 게임 캐릭터의 행동 로직 등 "지금 어떤 상태인지"와 "어떤 조건에서 다음 상태로 넘어가는지"가 명확한 시스템을 설명할 때 널리 쓰입니다.

왜 중요한가

유한상태기계는 시스템의 동작을 명확한 상태와 전이 규칙으로 표현하기 때문에, 설계 단계에서 논리적 오류를 미리 찾아내고 자동으로 검증하기에 유리합니다. 그래서 통신 프로토콜, 임베디드 시스템, 게임 AI, 사용자 인터페이스 흐름 설계 등 "지금 어떤 상태인가"가 시스템 동작을 좌우하는 다양한 소프트웨어·하드웨어 공학 분야에서 설계 모델로 널리 채택됩니다. 상태와 전이가 명시적으로 드러나 있어 형식 검증이나 모델 체킹 같은 자동화된 검증 기법과도 잘 결합됩니다.

논문에서는 이렇게 쓰입니다

"제안한 프로토콜의 동작은 유한상태기계로 모델링되었으며, 각 상태 전이는 형식 검증 도구를 통해 안전성이 확인되었다."

이 문장은 "시스템이 가질 수 있는 모든 상태와 그 사이의 전이 규칙을 정리한 뒤, 예상치 못한 상태로 빠지지 않는지 자동으로 검증했다"는 뜻입니다. 통신 프로토콜, 임베디드 시스템, 컴파일러의 어휘 분석기(lexer) 설계 등에서 자주 사용됩니다.

"게임 캐릭터의 행동 로직은 순찰, 추격, 공격 상태를 갖는 유한상태기계로 구현되었으며, 각 상태는 플레이어와의 거리 조건에 따라 전이되었다."

게임 AI 연구에서는 캐릭터의 행동 패턴을 몇 가지 상태와 전이 조건으로 단순화해 예측 가능하면서도 관리하기 쉬운 로직을 구현하는 데 이 모델을 사용합니다.

"차량용 임베디드 제어기의 동작 모드는 유한상태기계로 설계되었으며, 센서 이상 발생 시 안전 모드로 전이되도록 구성하였다."

임베디드·자동차 시스템 분야에서는 오류나 이상 상황에서 시스템이 안전한 상태로 전이되도록 설계하는 근거로 유한상태기계가 활용됩니다.

조금 더 깊게 보면

유한상태기계는 출력이 현재 상태만으로 결정되는 무어 머신(Moore machine)과, 현재 상태와 입력의 조합으로 결정되는 밀리 머신(Mealy machine)으로 구분되며, 이 구분은 하드웨어 회로 설계 논문 등에서 자주 언급됩니다. 또한 상태 수가 유한하다는 제약 때문에 스택처럼 무제한 저장 공간이 필요한 문제(예: 중첩된 괄호 검사)는 표현할 수 없어, 이런 경우에는 더 강력한 계산 모델인 푸시다운 오토마타로 확장해야 합니다.

주의할 점

유한상태기계는 "상태의 개수가 유한하다"는 전제를 깔고 있습니다. 상태나 조건이 무한히 늘어날 수 있는 복잡한 시스템(예: 스택을 활용하는 문법 분석)은 유한상태기계만으로는 표현할 수 없고, 더 강력한 모델(푸시다운 오토마타 등)이 필요합니다. 또한 상태 전이 로직이 제어구조의 조건문과 비슷해 보이지만, 유한상태기계는 "현재 상태"라는 개념을 명시적으로 관리한다는 점에서 차이가 있습니다.