유한상태기계로 상태 전이와 제어 로직 모델링하기

상태가 바뀌는 조건을 모델로 드러내기

유한상태기계(Finite State Machine, FSM), 또는 유한 오토마타(Finite Automaton, FA)는 컴퓨터 프로그램과 전자 논리 회로의 동작을 설계할 때 쓰는 수학적 모델이다. 이 모델은 유한한 상태만 가질 수 있으며, 어느 시점이든 시스템은 하나의 상태에만 있다. 특정 사건이 발생하면 정해진 규칙에 따라 다른 상태로 이동한다.

디지털 회로, 컴파일러, 프로토콜, 게임 AI처럼 동작 단계와 전환 조건이 분명한 대상에서 특히 유용하다. 입력을 받으면 전이 조건을 확인하고, 상태를 바꾸며, 그 결과로 출력을 낸다. 상태 다이어그램과 상태 전이 테이블은 이 흐름을 표현하는 대표적인 방법이다.

상태·사건·전이가 만드는 구조

FSM에서 상태는 시스템이 현재 놓여 있는 위치다. 가능한 상태 수는 유한하고, 여러 상태를 동시에 유지하지 않는다. 다이어그램에서는 보통 원이나 사각형으로 나타낸다.

사건은 상태 변경을 촉발하는 조건이다. 입력 신호, 타이머, 외부 트리거가 사건이 될 수 있으며, 상태 다이어그램에서는 화살표 위 레이블로 표시한다. 전이는 사건이 발생했을 때 한 상태에서 다른 상태로 이동하는 관계다. 자가 전이와 조건부 전이도 전이의 형태에 포함된다.

⤢✕

현재 상태와 입력으로 다음 상태를 정한다

상태 전이는 현재 상태와 입력 사건을 기준으로 다음 상태를 결정하는 과정이다. 이를 전이 함수로 쓰면 다음과 같다.

• δ(현재 상태, 입력) = 다음 상태
• 예: δ(S0, E1) = S1

전이 테이블은 가능한 입력마다 시스템이 어디로 이동하는지 빠짐없이 확인하는 데 적합하다.

현재 상태	입력 E1	입력 E2	입력 E3
S0	S1	S0	-
S1	S1	S2	S0
S2	-	S2	S0

아래 흐름에서는 처리 중인 작업이 취소되면 유휴 상태로 돌아가고, 완료된 뒤에도 리셋을 통해 다시 유휴 상태로 전환된다.

⤢✕

출력 규칙에 따른 Mealy와 Moore 머신

Mealy 머신은 현재 상태와 입력을 함께 사용해 출력을 결정한다. 입력이 변하면 출력도 빠르게 반응하며, 전이 화살표에 입력과 출력을 표시한다. 순서 검출기와 프로토콜에 적용할 수 있다.

Moore 머신의 출력은 현재 상태에만 의존한다. 출력은 상태가 바뀔 때만 변하고, 상태 내부에 출력값을 표시한다. 제어 시스템과 순차 회로에 쓰인다.

항목	Mealy	Moore
출력 결정	상태 + 입력	상태만
출력 변화	입력 변화 시 즉시	상태 변화 시만
상태 수	적음	많음
안정성	낮음	높음

회로와 소프트웨어의 제어 흐름에 적용하기

디지털 회로에서는 순차 논리 회로, 카운터, 타이머, 제어 유닛, 통신 프로토콜의 동작을 FSM으로 표현할 수 있다.

⤢✕

소프트웨어에서는 파서와 컴파일러, 네트워크 프로토콜의 TCP/IP 상태, 게임 캐릭터 AI, UI 상태 관리가 FSM의 적용 대상이다. 임베디드 시스템에서는 신호등, 자동문, 엘리베이터, 세탁기처럼 정해진 조건에 따라 제어 단계가 달라지는 장치에 활용된다.

요구사항에서 구현까지 상태를 고정하는 방법

먼저 필요한 상태를 식별하고, 발생할 수 있는 사건과 각 전이 조건을 명세한다. 이어 상태 다이어그램으로 흐름을 검토한 뒤, 상태 전이 테이블로 모든 상태와 입력의 조합을 확인한다.

⤢✕

현재 상태	시작	일시정지	재개	완료	취소	리셋
대기	실행	-	-	-	-	-
실행	-	일시정지	-	완료	-	-
일시정지	-	-	실행	-	대기	-
완료	-	-	-	-	-	대기

구현 단계에서는 하드웨어라면 플립플롭과 조합 논리를 사용하고, 소프트웨어라면 switch-case 또는 상태 패턴으로 전이 규칙을 구성할 수 있다. 상태와 사건, 전이를 분리해 두면 복잡한 시스템도 제어 흐름을 명확하게 모델링할 수 있다.