Конечные автоматы

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

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

Слово w ∈ Σ* принимается, если δ̂(q₀, w) ∈ F (расширенная функция переходов).

Язык L(A) — множество всех принятых слов.

Пример: ДКА для бинарных строк, делящихся на 3: состояния — остатки {0, 1, 2}. q₀ = F = {0}. δ(q, 0) = 2q mod 3, δ(q, 1) = (2q+1) mod 3.

Недетерминированные автоматы (НКА)

НКА: δ: Q×(Σ∪{ε}) → 2^Q (множество состояний, ε-переходы).

Принимает w, если существует путь, приводящий в принимающее состояние.

Теорема (Рабин–Скотт): ДКА и НКА эквивалентны по распознаваемым языкам (конструкция подмножеств).

Регулярные языки и выражения

Регулярные выражения строятся из: ∅, ε, a∈Σ, R₁∪R₂, R₁·R₂, R*.

Теорема Клини: Язык регулярен ⟺ распознаётся ДКА ⟺ задаётся регулярным выражением.

Лемма о разрастании (pumping lemma): Для доказательства нерегулярности. Если L регулярен, то существует p такое, что любое w∈L с |w|≥p представимо как w=xyz, где y∉ε, |xy|≤p, xyⁿz∈L для всех n≥0.

Канторский язык {aⁿbⁿ: n≥0} нерегулярен — насосная лемма даёт противоречие.

Минимальные автоматы и синтаксические моноиды

Для каждого регулярного языка существует единственный (до изоморфизма) минимальный ДКА с наименьшим числом состояний. Алгоритм Хопкрофта минимизирует ДКА за O(n log n). Идея: разбиение состояний на классы неразличимости — рефайнмент по поведению переходов.

Синтаксический моноид языка L — фактор-моноид (Σ*)/(≡_L), где u ≡_L v ⟺ для всех x,y: xuy ∈ L ↔ xvy ∈ L. L регулярен ↔ синтаксический моноид конечен. L — без звезды (star-free) ↔ апериодичен (нет ненулевых нильпотентных элементов). Связь с теорией полугрупп глубока.

Детерминистические vs. недетерминистические автоматы

ДКА и НКА распознают одинаковые языки (регулярные), но НКА может быть экспоненциально компактнее. Известно: существует язык, чей минимальный НКА имеет n состояний, а минимальный ДКА — 2ⁿ (конструкция «subset construction» из n-состоянного НКА даёт 2ⁿ состояний в худшем случае). Это «gap» между детерминизмом и недетерминизмом — один из ключевых разрывов в теории сложности.

Двусторонние автоматы (2DFA): автомат с головкой, движущейся в обе стороны по входу. Распознаёт ровно те же языки, что и ДКА (регулярные). Доказательство: конструктивный перевод 2DFA → ДКА (Шепердсон, 1959). Однако 2DFA может быть экспоненциально компактнее ДКА.

Регулярные языки и алгебра Буля

Операции над регулярными языками (объединение, пересечение, дополнение, конкатенация, звезда Клини) сохраняют регулярность. Алгебра регулярных выражений = алгебра Клини. Теорема Клини (1956): язык описывается регулярным выражением тогда и только тогда, когда распознаётся конечным автоматом — фундаментальная эквивалентность, положившая начало формальной теории языков.

Алгоритмы: Пустота регулярного языка: O(n) (DFS/BFS). Включение L₁ ⊆ L₂: проверить L₁ ∩ ¬L₂ = ∅. Эквивалентность двух ДКА: O(n²) через разбиение, или O(n log n) через Хопкрофта. Все эти задачи разрешимы — в отличие от задач для КСГ и ТМ.

ω-автоматы и бесконечные языки

Автоматы Бюхи: акцептируют бесконечные слова (ω-слова). Принимают ω-слово, если бесконечно часто посещают принимающее состояние. Аналог: нескольких финальных состояний для конечных слов. Детерминированные vs. недетерминированные: для Бюхи детерминированные строго слабее — распознают не все ω-регулярные языки. Автоматы Мюллера, Рабина, Стривта: более мощные классы детерминированных ω-автоматов. Применение: верификация бесконечных вычислений, LTL model checking.

Формальные грамматики и естественные языки

Иерархия Хомского применяется в лингвистике: естественные языки не вполне регулярны (зависимость через предложение), но и не полностью контекстно-зависимы. Тезис Хомского: трансформационно-порождающие грамматики лучше описывают синтаксис. В NLP: CFG и вероятностные CFG (PCFG) — основа парсинга (алгоритм CYK за O(n³|G|)). Современные трансформеры (BERT, GPT) эмпирически превосходят формальные грамматики в задачах NLP.

Регулярные выражения и их вычислительная сложность

Поиск регулярного выражения длиной m в тексте n: детерминированный КА → O(n·2^m) компиляция, O(n) поиск. Недетерминированный КА → O(nm) компиляция, O(nm) поиск. Проблема экспоненциального откатывания (ReDoS): небрежно написанные регулярные выражения на движках с обратным трекингом → экспоненциальное время в худшем случае. Безопасные движки: Russ Cox RE2, Google RE2, Rust's regex — основаны на NFA без обратного трекинга → линейное время. Применение в безопасности: ReDoS уязвимость (Catastrophic backtracking) в cloudflare, Atom IDE.

Автоматы и криптографические потоковые шифры

Линейный регистр сдвига с обратной связью (LFSR): последовательность aₙ = Σcᵢaₙ₋ᵢ mod 2, cᵢ ∈ {0,1}. Максимальный период = 2ⁿ−1 (m-последовательность) при неприводимом и примитивном характеристическом полиноме. Автокорреляция m-последовательностей почти нулевая — хорошие псевдослучайные свойства. Нелинейные комбинации LFSR: современные потоковые шифры (Grain, Trivium). Атака линейной аппроксимации Геффе: линейная сложность короткой LFSR угрожает безопасности.

Численный пример: построение ДКА и его работа

Задача: Построить ДКА для L={w∈{0,1}*: w заканчивается на «01»} и проверить несколько строк.

Шаг 1: Состояния: q₀ (ничего значимого), q₁ (последний символ — «0»), q₂ (последние два — «01», финальное).

Шаг 2: Таблица переходов: δ(q₀,0)=q₁; δ(q₀,1)=q₀; δ(q₁,0)=q₁; δ(q₁,1)=q₂; δ(q₂,0)=q₁; δ(q₂,1)=q₀.

Шаг 3: Проверка w=«1001»: q₀→(1)q₀→(0)q₁→(0)q₁→(1)q₂∈F. ∈L ✓. Проверка w=«010»: q₀→(0)q₁→(1)q₂→(0)q₁∉F. ∉L ✓.

Шаг 4: Минимальность: все три состояния различимы. Регулярное выражение: (0+1)*01. Связь с LFSR: для LFSR длины 3 (период ≤7) детерминированный КА с 2³=8 состояниями (содержимое регистра) распознаёт его цикл — атака Geffe использует именно эту линейную структуру для атаки на слабо нелинейные шифры.