FSM (Finite State Machine)

📌 FSM

FSM (Finite State Machine, конечный автомат) — формальная модель вычислительной системы или процесса, основанная на конечном числе состояний, переходах между ними, определяемых входными сигналами и текущим состоянием. FSM описывает поведение системы как последовательность состояний и управляющих переходов, что широко используется в цифровой логике, проектировании аппаратуры, системах управления, протоколах связи, программировании и моделировании процессов.

🧠 Как работает

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

Набор состояний (S): конечный, фиксированный перечень состояний, в которых может находиться система.
Входной алфавит (I): множество возможных входных сигналов или событий, влияющих на переходы.
Функция переходов (δ): отображение текущего состояния и входного сигнала в следующее состояние —
δ: S × I → S.
Начальное состояние (s₀): одно из состояний, в котором система стартует.
(Опционально) Набор выходных сигналов (O): определяет реакцию автомата.
(Опционально) Функция выходов (λ): зависимости выхода от состояний или переходов — различают автоматы Мили и Мура.

Классификация FSM

Детерминированный конечный автомат (DFA): в каждом состоянии и для каждого входа определён ровно один переход.
Недетерминированный конечный автомат (NFA): может иметь несколько переходов по одному входу или переходы без входа (ε-переходы).
Автомат Мура: выходы зависят только от состояния.
Автомат Мили: выходы зависят от состояния и входа.

Формальное описание

FSM можно формализовать как кортеж:

[ FSM = (S, I, O, \delta, \lambda, s_0) ]

(S) — конечное множество состояний,
(I) — множество входных символов,
(O) — множество выходных символов,
(\delta: S \times I \to S) — функция перехода,
(\lambda: S \to O) (для автомата Мура) или (\lambda: S \times I \to O) (для автомата Мили),
(s_0 \in S) — начальное состояние.

Работа FSM

Система стартует из состояния (s_0).
При поступлении входного сигнала (i \in I), система по функции (\delta) переходит в состояние (s’ = \delta(s, i)).
В зависимости от типа автомата, формируется выходной сигнал (o = \lambda(s)) или (o = \lambda(s, i)).
Процесс повторяется при новых входных данных.

Схема FSM (простой пример автомат Мура)

flowchart TD
    S0["S0: Initial"]
    S1["S1"]
    S2["S2"]
    S3["S3"]

    S0 -- "input=0" --> S0
    S0 -- "input=1" --> S1
    S1 -- "input=0" --> S2
    S1 -- "input=1" --> S1
    S2 -- "input=0" --> S0
    S2 -- "input=1" --> S3
    S3 -- "input=0" --> S2
    S3 -- "input=1" --> S1

Расширенная схема FSM с входами и выходами

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : input=1 / output=0
    S1 --> S2 : input=0 / output=1
    S2 --> S0 : input=0 / output=0
    S2 --> S3 : input=1 / output=1
    S3 --> S2 : input=0 / output=0
    S3 --> S1 : input=1 / output=1

⚙️ Где применяется

Аппаратное проектирование: управление цифровыми схемами, микропроцессорами, шинами, протоколами передачи, контроллерами памяти.
Системы ввода-вывода: USB, Ethernet, SPI, I2C, UART — в протоколах и их контроллерах.
Программирование: анализ лексики и синтаксиса, распознавание паттернов, UI, игровые механики.
Автоматика и робототехника: управление процессами, сигнализация, датчики, машины состояний.
Компиляторы: построение парсеров, регулярных выражений.
Системы реального времени и RTOS: планировщики, таймеры, прерывания.
Тестирование и моделирование: проверка логики, формальные методы.

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

Детерминированность и предсказуемость: чёткие состояния и переходы, легко анализировать и тестировать.
Простота реализации: в цифровой логике, аппаратуре, ПО.
Модульность: FSM легко разбиваются на подмодули.
Высокая скорость работы: подходит для аппаратных реализаций с малыми задержками.
Универсальность: применяется во множестве областей, от железа до алгоритмов.

❌ Недостатки

Ограниченность: конечное число состояний ограничивает сложность модели.
Комбинаторный взрыв: количество состояний может расти экспоненциально при усложнении системы.
Трудности масштабирования: большие FSM тяжело читать, поддерживать, оптимизировать.
Отсутствие памяти: FSM не хранит историю, кроме текущего состояния (для сложных задач нужна расширенная логика).
Невозможность описать все вычислимые функции: по сравнению с Тьюринг-машиной.

🔗 Связанные технологии

Microcontroller, CPU, State Machine, VHDL, Verilog, HDL, Protocol, RTOS, Mealy, Moore, Formal Verification, Parser, Compiler, FPGA

Резюме

FSM — фундаментальная модель для описания дискретных систем с конечным числом состояний и переходов, широко используемая в аппаратуре и программировании. Позволяет структурировать поведение систем, реализовывать протоколы, контроллеры и алгоритмы управления с ясной логикой переходов. Ограничена по объёму памяти и сложностям, но при грамотном использовании обеспечивает надёжность и предсказуемость работы.

Примеры кода

VHDL: простой FSM на 3 состояния

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
 
entity fsm_example is
    Port ( clk : in STD_LOGIC;
           rst : in STD_LOGIC;
           input_signal : in STD_LOGIC;
           output_signal : out STD_LOGIC);
end fsm_example;
 
architecture Behavioral of fsm_example is
    type state_type is (S0, S1, S2);
    signal state, next_state : state_type;
begin
    process(clk, rst)
    begin
        if rst = '1' then
            state <= S0;
        elsif rising_edge(clk) then
            state <= next_state;
        end if;
    end process;
 
    process(state, input_signal)
    begin
        case state is
            when S0 =>
                if input_signal = '1' then
                    next_state <= S1;
                else
                    next_state <= S0;
                end if;
            when S1 =>
                if input_signal = '0' then
                    next_state <= S2;
                else
                    next_state <= S1;
                end if;
            when S2 =>
                next_state <= S0;
            when others =>
                next_state <= S0;
        end case;
    end process;
 
    output_signal <= '1' when state = S2 else '0';
end Behavioral;

C: программная реализация FSM

typedef enum {S0, S1, S2} State;
 
State fsm(State current, int input) {
    switch(current) {
        case S0:
            return (input == 1) ? S1 : S0;
        case S1:
            return (input == 0) ? S2 : S1;
        case S2:
            return S0;
        default:
            return S0;
    }
}
 
int main() {
    State state = S0;
    int inputs[] = {0,1,0,1,0};
    for (int i = 0; i < 5; i++) {
        state = fsm(state, inputs[i]);
        printf("State: %d\n", state);
    }
    return 0;
}

Источники:
Hopcroft & Ullman “Introduction to Automata Theory”, IEEE Std 1016 (UML State Machine), Harel “Statecharts”, osdev.org, habr.com, Википедия, Xilinx/Altera FPGA docs, ARM Cortex-M docs, VHDL/Verilog textbooks, ACM publications.

OpenXF

Explorer