Finite-State Machine

이번 시간에는 유한 상태 기계(Finite-State Machine)를 소개하겠습니다.

이런 코드를 보신 적 있으실 겁니다.

if is_loading:
    ...
elif has_error and not is_loading:
    ...
elif is_submitted and has_error:
    ...

불리언 플래그가 세 개면 조합은 여덟 가지입니다. 그런데 실제로 의미 있는 상태는 서너 개뿐이고, 나머지는 ‘있어서는 안 되는’ 조합입니다.

문제는 그 ‘있어서는 안 되는’ 조합이 코드 어디에도 적혀 있지 않다는 점입니다. 개발자의 머릿속에만 있죠.

유한 상태 기계는 이 문제를 정반대 방향에서 접근합니다. 가능한 상태를 전부 나열하고, 그 사이를 오가는 길만 허용하는 것입니다.

유한 상태 기계란?

유한 상태 기계(Finite-State Machine, FSM)는 유한한 개수의 상태 중 정확히 하나에 머물러 있는 계산 모델입니다.

입력을 하나 받으면 정해진 규칙에 따라 다른 상태로 옮겨 갑니다. 이 이동을 전이(transition)라고 부릅니다.

구성 요소는 다섯 가지입니다.

지하철 개찰구를 예로 들어 보겠습니다. 잠겨 있는 상태에서 동전을 넣으면 풀리고, 풀린 상태에서 밀고 들어가면 다시 잠깁니다.

잠긴 상태에서 밀면 어떻게 될까요? 아무 일도 일어나지 않고 그대로 잠겨 있습니다.

이 ‘아무 일도 일어나지 않음’을 명시적으로 그려 넣는 것이 FSM의 핵심입니다. 플래그 조합에서는 이런 경우가 그냥 비어 있었죠.

상태 전이 표

상태 다이어그램은 같은 내용을 표로도 쓸 수 있습니다. 행이 상태, 열이 입력입니다.

빈칸이 하나도 없다는 점을 눈여겨봐 주세요. 상태 2개에 입력 2개면 칸은 정확히 4개이고, 모든 칸이 채워져야 기계가 완성됩니다.

설계 단계에서 빈칸이 보인다면 그것은 아직 결정하지 않은 동작입니다. 코드로 쓰기 전에 표에서 먼저 걸러낼 수 있는 것이죠.

짧은 역사

FSM의 뿌리는 1943년 McCulloch와 Pitts가 신경망을 수학적으로 기술하려고 만든 모델입니다.

1955년 Mealy와 1956년 Moore가 각각 출력을 내는 기계를 정리했고, 같은 해 Kleene이 정규표현식과 유한 오토마타가 같은 표현력을 가진다는 것을 증명했습니다.

1959년에는 Rabin과 Scott이 비결정론적 유한 오토마타를 도입하면서, 오늘날 교과서에 실린 형태가 완성되었습니다. 두 사람은 이 연구로 1976년 튜링상을 받았습니다.

받개와 변환기

FSM은 출력을 내는 방식에 따라 크게 두 갈래로 나뉩니다.

받개

받개(Acceptor)는 입력을 끝까지 읽은 뒤 ‘예’ 또는 ‘아니오’만 답하는 기계입니다.

마지막에 도착한 상태가 종료 상태이면 받아들이고, 아니면 거부합니다. 정규표현식이 문자열을 검사하는 방식이 바로 이것입니다.

아래는 a가 0개 이상 나온 뒤 b로 끝나는 문자열만 받아들이는 기계입니다.

Q2는 한 번 빠지면 나올 수 없는 상태입니다. 이런 상태를 죽은 상태(dead state)라고 부르는데, 조건을 이미 어겼으니 남은 입력을 아무리 읽어도 결과가 바뀌지 않습니다.

변환기: Moore와 Mealy

변환기(Transducer)는 상태를 옮겨 다니면서 출력을 만들어 냅니다. 출력을 어디에 붙이느냐에 따라 두 가지로 나뉩니다.

Moore 기계는 출력이 오직 현재 상태에만 달려 있습니다. 상태에 이름표처럼 출력이 붙어 있는 형태죠.

Mealy 기계는 출력이 상태와 입력의 조합에 달려 있습니다. 출력이 상태가 아니라 화살표에 붙습니다.

어느 쪽이 더 나을까요? 표현력은 같습니다. 두 모델은 서로 변환할 수 있습니다.

차이는 타이밍에 있습니다. Moore는 상태가 바뀐 뒤에 출력이 정해지므로 한 박자 늦고, Mealy는 입력을 받는 순간 출력이 나오므로 상태 수가 더 적어지는 경향이 있습니다.

하드웨어 설계에서는 이 한 박자가 중요합니다. Moore 쪽이 타이밍을 예측하기 쉬워 회로에서 선호되는 편이죠.

결정론과 비결정론

지금까지 본 기계들은 상태와 입력이 정해지면 다음 상태가 하나로 결정되었습니다. 이런 기계를 결정론적 유한 오토마타(DFA)라고 부릅니다.

비결정론적 유한 오토마타

비결정론적 유한 오토마타(NFA)는 이 제약을 풀어 줍니다. 하나의 입력에 대해 갈 수 있는 상태가 여러 개여도 되고, 아예 없어도 됩니다.

심지어 입력을 읽지 않고 상태를 옮기는 전이(ε-전이)도 허용됩니다.

그렇다면 NFA가 DFA보다 강력할까요? 직관적으로는 그럴 것 같지만, 답은 ‘아니오’입니다.

부분집합 구성

모든 NFA는 그와 동등한 DFA로 바꿀 수 있습니다. 이를 부분집합 구성(subset construction) 또는 멱집합 구성이라고 합니다.

아이디어는 단순합니다. NFA가 ‘지금 있을 수 있는 상태들의 집합’을 통째로 DFA의 상태 하나로 삼는 것입니다.

즉 NFA가 {Q1, Q3} 중 어디엔가 있다는 상황을, DFA에서는 Q13이라는 이름의 상태 하나로 부르는 셈이죠.

대신 상태 수가 늘어납니다. NFA의 상태가 n개라면 부분집합은 최대 2^n개이므로, 최악의 경우 DFA의 상태 수는 지수적으로 폭증합니다. 실무에서 NFA를 그대로 시뮬레이션하는 구현이 흔한 이유입니다.

정규표현식과의 관계

정규표현식과 유한 오토마타가 같은 것을 표현한다는 사실은 앞서 말씀드린 대로 Kleene이 증명했습니다.

그래서 정규표현식 엔진은 대체로 이런 순서로 동작합니다.

정규표현식 → NFA → (선택) DFA → 매칭

정규표현식을 NFA로 바꾸는 표준적인 방법이 1968년 Ken Thompson이 발표한 톰슨 구성(Thompson’s construction)입니다. 각 연산자마다 대응하는 작은 NFA 조각을 정해 두고, 그것들을 조립해 나가는 방식이죠.

세 가지 구현 방법

이제 실제 코드로 내려와 보겠습니다. 앞서 본 개찰구를 세 가지 방식으로 구현해 보죠.

1. 조건문

가장 먼저 떠오르는 방법입니다.

def transition(state: str, event: str) -> str:
    if state == "LOCKED":
        if event == "coin":
            return "UNLOCKED"
        return "LOCKED"

    if state == "UNLOCKED":
        if event == "push":
            return "LOCKED"
        return "UNLOCKED"

    raise ValueError(f"unknown state: {state}")

상태가 두세 개일 때는 이만한 것이 없습니다. 의존성도 없고 읽기도 쉽습니다.

다만 상태가 늘어나면 중첩이 깊어지고, 빠뜨린 조합이 있어도 눈에 띄지 않습니다. 앞에서 지적한 플래그 문제가 다른 모습으로 돌아오는 셈이죠.

2. 전이 테이블

전이 함수를 코드가 아니라 데이터로 표현하는 방법입니다.

TRANSITIONS = {
    ("LOCKED",   "coin"): "UNLOCKED",
    ("LOCKED",   "push"): "LOCKED",
    ("UNLOCKED", "coin"): "UNLOCKED",
    ("UNLOCKED", "push"): "LOCKED",
}

def transition(state: str, event: str) -> str:
    return TRANSITIONS[(state, event)]

앞서 그린 상태 전이 표가 그대로 코드가 되었습니다. 표에 빈칸이 있으면 딕셔너리에 키가 없으니 바로 예외로 드러납니다.

전이 규칙을 JSON이나 YAML로 빼서 코드 수정 없이 바꾸는 것도 가능합니다. 테이블을 순회하면 도달할 수 없는 상태를 찾아내는 검증 코드도 쉽게 붙일 수 있죠.

대신 전이할 때 부수 효과를 실행해야 한다면 테이블만으로는 부족해서, 값에 함수를 얹는 구조가 필요해집니다.

3. 상태 패턴

상태마다 클래스를 하나씩 두고, 각 클래스가 자기 전이를 책임지는 방법입니다.

class Locked:
    def coin(self): return Unlocked()
    def push(self): return self

class Unlocked:
    def coin(self): return self
    def push(self): return Locked()

분기문이 사라지고, 새 상태를 추가할 때 기존 클래스를 건드릴 필요가 없습니다.

상태마다 들어올 때와 나갈 때 할 일이 다르다면 이 구조가 가장 깔끔합니다. on_enter, on_exit 같은 메서드를 각 클래스에 두면 되니까요.

물론 상태가 다섯 개면 클래스도 다섯 개입니다. 전체 전이를 한눈에 보려면 파일 다섯 개를 열어야 하죠.

무엇을 고를까

FSM이 할 수 없는 것

FSM은 만능이 아닙니다. 오히려 못 하는 일이 분명하다는 점이 이 모델의 특징입니다.

셀 수 없다

괄호가 짝이 맞는지 검사하는 문제를 FSM으로 풀 수 있을까요?

(()())처럼 중첩 깊이가 정해져 있다면 가능합니다. 깊이 1, 깊이 2, 깊이 3에 각각 상태를 배정하면 되니까요.

하지만 깊이에 제한이 없다면 불가능합니다. 상태의 개수가 유한한데 세어야 할 깊이는 무한하기 때문입니다.

이런 일을 하려면 스택이 필요하고, 스택을 붙인 모델이 푸시다운 오토마타(PDA)입니다.

정규표현식으로 HTML을 파싱하지 말라는 오래된 조언의 근거가 여기에 있습니다. 중첩 구조는 애초에 정규 언어가 아닙니다.

상태 폭발

두 번째 한계는 실무에서 훨씬 자주 만납니다.

독립적인 관심사가 늘어날 때마다 상태 수가 곱해집니다. 연결 상태 3가지와 인증 상태 3가지를 하나의 평면 FSM으로 표현하면 9개가 필요하죠.

여기에 재생 상태 4가지가 더해지면 36개가 됩니다. 사람이 그릴 수 있는 그림이 아닙니다.

해법은 상태를 계층으로 쌓는 것입니다. UML 상태 기계(statechart)는 상태 안에 상태를 중첩시키고, 서로 독립적인 관심사는 직교 영역으로 분리합니다.

평면 FSM으로 그렸을 때 다이어그램이 감당 안 될 정도로 커진다면, 대개 서로 독립적인 관심사 두 개가 한 기계에 섞여 있다는 신호입니다. 기계를 두 개로 쪼개는 쪽이 대부분 정답입니다.

어디에 쓰이고 있나

FSM은 이론 과목에만 나오는 개념이 아닙니다. 사실 거의 모든 곳에 이미 들어가 있습니다.

• 렉서와 토크나이저: 컴파일러가 소스 코드를 토큰으로 쪼갤 때 쓰는 것이 바로 DFA입니다.
• 정규표현식 엔진: 앞서 본 대로 정규표현식은 유한 오토마타로 변환되어 실행됩니다.
• 네트워크 프로토콜: TCP 연결은 LISTEN, SYN_SENT, ESTABLISHED, TIME_WAIT 같은 상태를 오가는 상태 기계입니다. RFC에 상태 다이어그램이 그대로 실려 있죠.
• UI 상태 관리: 폼이나 결제 화면처럼 단계가 정해진 흐름은 플래그보다 상태 기계로 표현하는 쪽이 안전합니다.
• 게임 AI: 순찰, 추적, 공격, 도주처럼 행동이 명확히 구분되는 NPC 로직의 고전적인 구현 방식입니다.
• 하드웨어 제어: 신호등, 엘리베이터, 자판기, CPU의 제어 유닛까지 전부 상태 기계로 설계됩니다.

연습 문제

LeetCode 65. Valid Number

숫자 형식이 올바른지 검사하는 문제입니다. 조건문으로 풀면 끝없이 늘어지지만, 상태 전이 표를 먼저 그리고 시작하면 훨씬 수월합니다. FSM 연습에는 이만한 문제가 없습니다.

LeetCode 8. String to Integer (atoi)

공백, 부호, 숫자, 그 외 문자를 순서대로 처리하는 문제입니다. 상태 4개짜리 전이 테이블로 정리하기 좋습니다.

LeetCode 393. UTF-8 Validation

바이트 시퀀스가 올바른 UTF-8인지 검사합니다. ‘남은 바이트 수’를 상태로 두면 자연스럽게 상태 기계가 됩니다.

참고 자료

• Finite-state machine — Wikipedia
• Nondeterministic finite automaton — Wikipedia
• Powerset construction — Wikipedia
• Thompson’s construction — Wikipedia
• Mealy machine — Wikipedia
• Moore machine — Wikipedia
• UML state machine — Wikipedia
• RFC 9293: Transmission Control Protocol (TCP) — 연결 상태 다이어그램