Что такое конечный автомат?

Конечный автомат (Finite State Machine, FSM)

Конечный автомат — это математическая модель вычислений, которая определяет систему с конечным числом состояний. Система переходит между состояниями на основе входных событий. Это мощный инструмент для моделирования поведения в реальном времени.

Основные компоненты

Конечный автомат состоит из:

1. СОСТОЯНИЯ (States)
   - Конечное множество возможных состояний
   - Система может находиться только в ОДНОМ состоянии
   - Пример: idle, running, paused, stopped

2. СОБЫТИЯ (Events/Inputs)
   - Триггеры которые вызывают переходы
   - Пример: click, timer, error, user_input

3. ПЕРЕХОДЫ (Transitions)
   - Правила перехода из одного состояния в другое
   - На основе текущего состояния и события
   - Пример: idle + click → running

4. НАЧАЛЬНОЕ СОСТОЯНИЕ (Initial State)
   - Состояние когда система стартует
   - Пример: idle

5. ФИНАЛЬНЫЕ СОСТОЯНИЯ (Final/Accepting States)
   - Состояния когда процесс завершён
   - Опционально
   - Пример: stopped

Классический пример: Светофор

Светофор как FSM:

          ↓ timer=30s
    ┌────────────┐
    │   RED      │
    └────────┬───┘
             │
             ↓ timer=25s
    ┌────────────┐
    │   GREEN    │
    └────────┬───┘
             │
             ↓ timer=5s
    ┌────────────┐
    │   YELLOW   │
    └────────┬───┘
             │
             └─────────────┘

Состояния: RED, GREEN, YELLOW
События: timer=30s, timer=25s, timer=5s
Переходы: RED→GREEN, GREEN→YELLOW, YELLOW→RED

Практический пример на Python

from enum import Enum
from dataclasses import dataclass
from typing import Callable, Dict, Optional

class State(Enum):
    """Возможные состояния."""
    IDLE = "idle"
    LOADING = "loading"
    SUCCESS = "success"
    ERROR = "error"

class Event(Enum):
    """Возможные события."""
    START = "start"
    COMPLETE = "complete"
    FAIL = "fail"
    RETRY = "retry"

class SimpleFSM:
    def __init__(self):
        self.current_state = State.IDLE
        # Таблица переходов: (state, event) -> new_state
        self.transitions: Dict[tuple, State] = {
            (State.IDLE, Event.START): State.LOADING,
            (State.LOADING, Event.COMPLETE): State.SUCCESS,
            (State.LOADING, Event.FAIL): State.ERROR,
            (State.ERROR, Event.RETRY): State.LOADING,
            (State.SUCCESS, Event.START): State.LOADING,
        }
    
    def handle_event(self, event: Event) -> bool:
        """Обработать событие и перейти в новое состояние."""
        key = (self.current_state, event)
        
        if key not in self.transitions:
            print(f"❌ Переход невозможен: {self.current_state} + {event}")
            return False
        
        new_state = self.transitions[key]
        print(f"✓ Переход: {self.current_state.value} → {new_state.value}")
        self.current_state = new_state
        return True

# Использование
fsm = SimpleFSM()
print(f"Начальное состояние: {fsm.current_state.value}")

fsm.handle_event(Event.START)      # idle → loading
fsm.handle_event(Event.COMPLETE)   # loading → success
fsm.handle_event(Event.START)      # success → loading
fsm.handle_event(Event.FAIL)       # loading → error
fsm.handle_event(Event.RETRY)      # error → loading
fsm.handle_event(Event.COMPLETE)   # loading → success
fsm.handle_event(Event.FAIL)       # ❌ Невозможно (success + fail = не определён)

Пример: Управление заказом в интернет-магазине

from enum import Enum

class OrderState(Enum):
    PENDING = "pending"          # Ожидание подтверждения
    CONFIRMED = "confirmed"      # Подтверждён
    SHIPPED = "shipped"          # Отправлен
    DELIVERED = "delivered"      # Доставлен
    CANCELLED = "cancelled"      # Отменён

class OrderEvent(Enum):
    CONFIRM = "confirm"
    SHIP = "ship"
    DELIVER = "deliver"
    CANCEL = "cancel"
    REFUND = "refund"

class Order:
    def __init__(self, order_id: str):
        self.order_id = order_id
        self.state = OrderState.PENDING
        self.history = [(OrderState.PENDING, None)]
    
    def handle_event(self, event: OrderEvent) -> bool:
        """Обработать событие."""
        transitions = {
            (OrderState.PENDING, OrderEvent.CONFIRM): OrderState.CONFIRMED,
            (OrderState.PENDING, OrderEvent.CANCEL): OrderState.CANCELLED,
            (OrderState.CONFIRMED, OrderEvent.SHIP): OrderState.SHIPPED,
            (OrderState.CONFIRMED, OrderEvent.CANCEL): OrderState.CANCELLED,
            (OrderState.SHIPPED, OrderEvent.DELIVER): OrderState.DELIVERED,
            (OrderState.SHIPPED, OrderEvent.CANCEL): OrderState.CANCELLED,  # Отмена при доставке
            (OrderState.CANCELLED, OrderEvent.REFUND): OrderState.PENDING,  # Возврат
        }
        
        key = (self.state, event)
        if key not in transitions:
            return False
        
        old_state = self.state
        self.state = transitions[key]
        self.history.append((self.state, event))
        print(f"Заказ {self.order_id}: {old_state.value} → {self.state.value}")
        return True

# Сценарий 1: Успешная доставка
order1 = Order("ORD-001")
order1.handle_event(OrderEvent.CONFIRM)
order1.handle_event(OrderEvent.SHIP)
order1.handle_event(OrderEvent.DELIVER)
print(f"История: {[(s.value, e.value if e else None) for s, e in order1.history]}")

# Сценарий 2: Отмена перед доставкой
order2 = Order("ORD-002")
order2.handle_event(OrderEvent.CONFIRM)
order2.handle_event(OrderEvent.CANCEL)  # Отменили
order2.handle_event(OrderEvent.REFUND)   # Вернули
print(f"История: {[(s.value, e.value if e else None) for s, e in order2.history]}")

Более сложный пример: Telegram Bot FSM

from enum import Enum
from typing import Optional, Dict, List

class UserState(Enum):
    START = "start"
    CHOOSING_PRODUCT = "choosing_product"
    ENTERING_QUANTITY = "entering_quantity"
    CHECKOUT = "checkout"
    PAYMENT = "payment"
    COMPLETED = "completed"
    CANCELLED = "cancelled"

class UserEvent(Enum):
    START_SHOPPING = "start_shopping"
    SELECT_PRODUCT = "select_product"
    ENTER_QUANTITY = "enter_quantity"
    GO_TO_CHECKOUT = "go_to_checkout"
    CONFIRM_PAYMENT = "confirm_payment"
    PAYMENT_SUCCESS = "payment_success"
    PAYMENT_FAILED = "payment_failed"
    CANCEL = "cancel"
    RETRY = "retry"

class UserFSM:
    def __init__(self, user_id: int):
        self.user_id = user_id
        self.state = UserState.START
        self.cart: List[Dict] = []
        self.current_quantity: Optional[int] = None
    
    def handle_event(self, event: UserEvent, **kwargs) -> bool:
        """Обработать событие с параметрами."""
        transitions = {
            (UserState.START, UserEvent.START_SHOPPING): UserState.CHOOSING_PRODUCT,
            (UserState.CHOOSING_PRODUCT, UserEvent.SELECT_PRODUCT): UserState.ENTERING_QUANTITY,
            (UserState.ENTERING_QUANTITY, UserEvent.ENTER_QUANTITY): UserState.CHOOSING_PRODUCT,
            (UserState.CHOOSING_PRODUCT, UserEvent.GO_TO_CHECKOUT): UserState.CHECKOUT,
            (UserState.CHECKOUT, UserEvent.CONFIRM_PAYMENT): UserState.PAYMENT,
            (UserState.PAYMENT, UserEvent.PAYMENT_SUCCESS): UserState.COMPLETED,
            (UserState.PAYMENT, UserEvent.PAYMENT_FAILED): UserState.CHECKOUT,
            (UserState.PAYMENT, UserEvent.RETRY): UserState.PAYMENT,
            (UserState.CHECKOUT, UserEvent.CANCEL): UserState.CANCELLED,
            (UserState.CHOOSING_PRODUCT, UserEvent.CANCEL): UserState.CANCELLED,
        }
        
        key = (self.state, event)
        if key not in transitions:
            print(f"❌ Невозможный переход: {self.state.value} + {event.value}")
            return False
        
        # Выполнить действие перед переходом
        self._on_event(event, **kwargs)
        
        # Перейти в новое состояние
        new_state = transitions[key]
        print(f"Пользователь {self.user_id}: {self.state.value} → {new_state.value}")
        self.state = new_state
        return True
    
    def _on_event(self, event: UserEvent, **kwargs):
        """Выполнить действие при событии."""
        if event == UserEvent.SELECT_PRODUCT:
            product = kwargs.get('product')
            self.cart.append({"product": product})
            print(f"  → Добавлен товар: {product}")
        
        elif event == UserEvent.ENTER_QUANTITY:
            quantity = kwargs.get('quantity')
            self.current_quantity = quantity
            print(f"  → Количество: {quantity}")
        
        elif event == UserEvent.PAYMENT_SUCCESS:
            print(f"  → Платёж успешен! Товары: {self.cart}")
            self.cart = []

# Использование
user = UserFSM(user_id=123)
user.handle_event(UserEvent.START_SHOPPING)
user.handle_event(UserEvent.SELECT_PRODUCT, product="Laptop")
user.handle_event(UserEvent.ENTER_QUANTITY, quantity=1)
user.handle_event(UserEvent.SELECT_PRODUCT, product="Mouse")
user.handle_event(UserEvent.ENTER_QUANTITY, quantity=2)
user.handle_event(UserEvent.GO_TO_CHECKOUT)
user.handle_event(UserEvent.CONFIRM_PAYMENT)
user.handle_event(UserEvent.PAYMENT_SUCCESS)
print(f"Финальное состояние: {user.state.value}")

Диаграмма состояний (State Diagram)

Пример: Медиа-плеер

         ┌─────────────────────┐
         │      STOPPED        │
         └────────┬────────────┘
                  │
              play│ resume
                  ↓
         ┌─────────────────────┐
         │      PLAYING        │<─────┐
         └────────┬────────────┘      │
                  │                   │
               pause                  │
                  ↓                   │
         ┌─────────────────────┐      │
         │      PAUSED         │      │
         └────────┬────────────┘      │
                  │                   │
            resume│                   │
                  └───────────────────┘
                  
                  stop (из любого состояния)
                    ↓
         ┌─────────────────────┐
         │      STOPPED        │
         └─────────────────────┘

Применение FSM в реальных системах

# 1. Workflow процессы
# Согласование документов: draft → submitted → approved → published

# 2. Игры
# Player states: idle → running → jumping → falling → idle

# 3. Сетевые протоколы
# TCP states: LISTEN → SYN_RECEIVED → ESTABLISHED → FIN_WAIT → CLOSED

# 4. Парсеры
# Лексический анализ, синтаксический анализ

# 5. Контроллеры (MVC)
# Управление состоянием приложения

# 6. Тестирование
# Model-based testing использует FSM

Преимущества FSM

✓ Ясность логики
  - Явно определены все допустимые переходы
  - Легко понять поведение системы
  - Нет "сюрпризов" и скрытых состояний

✓ Недопустимые состояния невозможны
  - Система не может перейти в некорректное состояние
  - Ошибки выявляются на этапе проектирования

✓ Тестирование
  - Легко покрыть все состояния и переходы
  - Можно сгенерировать все возможные сценарии

✓ Документирование
  - Диаграмма состояний это сама себя документирует
  - Код соответствует требованиям

Недостатки

❌ Взрывчатость состояний
  - Если параметров много → состояний может быть очень много
  - 10 булевых флагов = 2^10 = 1024 состояния
  - Решение: иерархические автоматы (Statecharts)

❌ Жёсткость
  - Тяжело добавить новые переходы
  - Нужно пересматривать всю таблицу переходов
  - Решение: использовать конфигурацию вместо hardcode

Ключевые моменты

• FSM имеет конечное число состояний
• Переходы зависят от текущего состояния и события
• Недопустимые переходы должны быть явно запрещены
• Диаграммы состояний помогают визуализировать логику
• Используется везде: игры, протоколы, workflow, парсеры
• Тестировать FSM проще чем тестировать if-else спагетти