Детерминированные конечные автоматы (DFA)

Каждый раз, когда вы набираете пароль на телефоне - звёздочки появляются по одной, и после нужного количества система решает: «пустить» или «не пустить». Это и есть конечный автомат - простейшая модель, которая читает вход символ за символом и принимает решение. За этой простотой скрывается механизм, на котором работают лексеры компиляторов, сетевые фильтры и движки регулярных выражений.

• **Лексический анализ** - компилятор GCC, интерпретатор Python используют DFA для разбора исходного кода на токены (числа, ключевые слова, операторы)
• **Сетевые фильтры** - Snort, Suricata сканируют трафик DFA-движками со скоростью гигабит в секунду
• **Контроллеры в hardware** - светофоры, лифты, торговые автоматы реализуют логику через конечные автоматы

Автомат как граф

**Вы каждый день пользуетесь конечными автоматами.** Турникет в метро - конечный автомат. Торговый автомат с кофе - конечный автомат. Светофор - тоже конечный автомат.

У каждого из них есть **состояния** (заблокирован / разблокирован) и **переходы** (вставил карту → разблокирован, прошёл → заблокирован). Вся суть: автомат находится в ОДНОМ состоянии в каждый момент времени и меняет его по чёткому правилу.

**Состояния** - это узлы графа (кружки). **Переходы** - это рёбра (стрелки с подписями). Один узел помечен как **стартовый** (→), некоторые - как **принимающие** (двойной кружок).

Теперь переведём это на язык формальных языков. Автомат **читает строку** символ за символом. Начинает в стартовом состоянии, по каждому символу делает переход. Если после прочтения ВСЕЙ строки оказался в принимающем состоянии - строка **принята**. Иначе - **отвергнута**.

Проверьте: строка "101". Старт в q0 → читаем '1' → q1 → читаем '0' → q0 → читаем '1' → q1. Оказались в q1 (принимающее) → строка принята!

Формальное определение DFA

Интуиция есть - пора зафиксировать определение. **DFA - это пятёрка** (кортеж из пяти элементов), где каждый элемент описывает одну грань автомата.

**DFA = (Q, Σ, δ, q₀, F)** - детерминированный конечный автомат полностью задан пятью компонентами.

**Ключевое слово - детерминированный.** Для каждой пары (состояние, символ) существует РОВНО ОДИН переход. Не ноль, не два - один. Автомат никогда не «сомневается», куда идти.

Запишем полную таблицу переходов для автомата «строки, заканчивающиеся на 1»:

В таблице переходов **→** помечает стартовое состояние, ***** помечает принимающее. Каждая ячейка содержит ровно одно состояние - это и есть детерминизм.

Построение DFA: три примера

Теория без практики мертва. Построим три DFA с нарастающей сложностью - от подсчёта символов до арифметики в двоичной системе.

Пример 1: Чётное число нулей

**Задача:** принять все строки из {0, 1}*, где количество символов '0' - чётное (0, 2, 4, ...). Пустая строка тоже подходит (0 - чётное число).

**Идея:** нам нужно отслеживать чётность количества нулей. Это ровно два состояния: «пока чётное» и «пока нечётное». Символ '1' не меняет счётчик.

Пример 2: Строки, заканчивающиеся на "01"

**Задача:** принять все строки из {0, 1}*, которые заканчиваются подстрокой "01".

**Идея:** нужно помнить, какой «суффикс» от паттерна "01" мы уже видели. Три состояния: ничего не совпало (q0), последний символ был '0' (q1), видели "01" на конце (q2).

Проверка: строка "1001". q0→1→q0→0→q1→0→q1→1→q2 ✓ Принята! Строка "100": q0→1→q0→0→q1→0→q1 - не в принимающем ✗

Пример 3: Бинарные числа, делящиеся на 3

**Задача:** строка из {0, 1}* представляет двоичное число. Принять, если число делится на 3.

**Ключевая идея:** отслеживаем остаток от деления на 3. При чтении нового бита число удваивается и прибавляется бит: `n' = 2n + bit`. Остаток: `r' = (2r + bit) mod 3`.

Этот приём работает для деления на ЛЮБОЕ число n: нужно n состояний (остатки 0..n-1), переходы по формуле (2r + bit) mod n. DFA для делимости на 5? Ровно 5 состояний!

Реализация DFA на Python

Формальная модель хороша, но мы - программисты. Реализуем DFA как класс на Python и посмотрим, как автомат обрабатывает строку **шаг за шагом**.

Создадим наш автомат для чётного числа нулей и протестируем:

Самое полезное - **трассировка**. Посмотрим, что происходит внутри автомата:

**Время работы DFA - O(n)**, где n - длина входной строки. Один проход, один переход на символ, никакого возврата. Это делает DFA идеальной моделью для потокового сканирования (лексеры компиляторов, сетевые фильтры).

Ключевые идеи

• **DFA = (Q, Σ, δ, q₀, F)** - пять компонентов полностью определяют автомат
• **Детерминизм** - для каждой пары (состояние, символ) ровно один переход, никакой неоднозначности
• **O(n) время** - DFA читает строку за один проход, один переход на символ
• **Состояния кодируют «память»** - DFA помнит только то, в каком состоянии находится, не историю вычислений

Связь с другими темами

DFA - центральный объект теории формальных языков, связанный со множеством тем:

• Регулярные выражения — Каждое регулярное выражение можно преобразовать в эквивалентный DFA (теорема Клини)
• NFA - недетерминированные автоматы — Следующий шаг: NFA допускает несколько переходов, но распознаёт те же языки
• Минимизация DFA — Для каждого регулярного языка существует единственный минимальный DFA

Вопросы для размышления

• DFA помнит только текущее состояние - конечный объём памяти. Какие задачи принципиально НЕЛЬЗЯ решить с ограниченной памятью? (Подсказка: попробуйте построить DFA для языка aⁿbⁿ)
• Если DFA для делимости на n требует n состояний, сколько состояний нужно для проверки делимости на n И на m одновременно?
• Компилятор использует DFA для лексического анализа. Почему именно DFA, а не более мощная модель?

Связанные уроки

• fl-05-regex — Regular expressions describe the same class as DFAs
• fl-07-nfa — NFA is a relaxed form of DFA - contrast highlights determinism
• fl-08-nfa-to-dfa — Subset construction converts NFA to equivalent DFA
• fl-10-dfa-minimization — Minimization reduces DFA to canonical smallest form
• comp-06-lexer-basics — Lexer implementation is a DFA running on character input