Детерминированный конечный автомат (ДКА)

Конечный автомат — простейшая вычислительная машина: горстка состояний и переходы по символам, без всякой памяти, кроме «где я сейчас».

ДКА — детерминированный конечный автомат: пятёрка (Q, Σ, δ, q₀, F), где из каждого состояния по каждому символу ведёт ровно один переход.

Пятёрка определения

ДКА формально задаётся пятью компонентами: Q — конечное множество состояний; Σ — входной алфавит; δ: Q × Σ → Q — функция переходов (по состоянию и символу даёт следующее состояние); q₀ ∈ Q — начальное состояние; F ⊆ Q — множество принимающих (финальных) состояний.

Работает он так: автомат начинает в q₀, читает строку слева направо по одному символу, на каждом шаге переходит по δ в новое состояние. Прочитав всю строку, смотрит на текущее состояние: если оно в F — строка принята, иначе отвергнута. Множество всех принятых строк — язык автомата L(M). Слово «детерминированный» означает: следующий шаг однозначно определён — никакого выбора.

Диаграмма и таблица переходов

Построим ДКА, принимающий двоичные строки, в которых чётное число единиц. Хватит двух состояний: q₀ (единиц прочитано чётно — оно же стартовое и принимающее) и q₁ (нечётно). Символ 0 не меняет чётность, символ 1 переключает состояние.

        0                 0
       ┌──┐             ┌──┐
       │  v             │  v
    ──>((q0))  --1-->    (q1)
          ^   <--1--      
          └────────────────┘

((q0)) — двойной кружок = принимающее состояние
──>     — стрелка в стартовое состояние

Та же информация в виде таблицы переходов (строки — состояния, столбцы — символы):

состояние	0	1	принимающее?
→ q0	q0	q1	да
q1	q1	q0	нет

Симуляция ДКА на Python

Любой ДКА — это просто словарь переходов плюс цикл по символам. Реализуем универсальный симулятор и прогоним наш автомат.

def run_dfa(delta, start, accept, word):
    state = start
    for ch in word:
        state = delta[(state, ch)]   # ровно один переход
    return state in accept

# ДКА: чётное число единиц
delta = {
    ("q0", "0"): "q0", ("q0", "1"): "q1",
    ("q1", "0"): "q1", ("q1", "1"): "q0",
}
for w in ["", "1", "11", "1010", "111"]:
    ok = run_dfa(delta, "q0", {"q0"}, w)
    print(f"{w or 'ε':>4} -> {'принята' if ok else 'отвергнута'}")

Вывод:

   ε -> принята
   1 -> отвергнута
  11 -> принята
1010 -> принята
 111 -> отвергнута

Пустая строка принята (ноль единиц — чётно), «11» принята, «111» отвергнута — ровно как задумано.

Как работает под капотом

Вся «память» ДКА — это его текущее состояние, а состояний конечное число. Значит, автомат различает лишь конечное число ситуаций. Это объясняет его силу и его предел: он распознаёт «чётность», «делимость на 3», «содержит подстроку abc» — всё, что сводится к конечному числу классов, — но не умеет считать до произвольного n. Запомнить «сколько именно единиц» он не может — только «чётно/нечётно». Эта ограниченность — суть будущей леммы о накачке.

Частые ошибки

Забыть переход для какого-то символа. В ДКА δ должна быть определена для каждой пары (состояние, символ). Если перехода нет — это уже не полный ДКА (иногда добавляют «ловушку» — мёртвое состояние).

Перепутать принимающее и стартовое. Стартовое одно, принимающих может быть несколько (или ноль). Состояние может быть и стартовым, и принимающим одновременно.

Думать, что пустую строку нельзя принять. Если q₀ ∈ F, то ε принимается — автомат ничего не читает и сразу проверяет стартовое состояние.

Итог

ДКА — пятёрка (Q, Σ, δ, q₀, F); из каждого состояния по каждому символу ровно один переход.
Строка принята, если после её прочтения автомат в принимающем состоянии; язык автомата — все принятые строки.
Диаграмма (кружки и стрелки, двойной кружок = принимающее) и таблица переходов — два способа задать δ.
Память ДКА — только текущее состояние; считать до произвольного n он не умеет.