Regex ↔ автоматы: теорема Клини

Когда вы пишете `grep 'error|warn' log.txt`, за кулисами происходит цепочка: ваш regex превращается в NFA, NFA - в DFA, и DFA сканирует файл за один проход. А когда Python проверяет regex `(a+)+` на строке из 30 символов, он зависает на минуты. Почему grep мгновенный, а Python тормозит? Ответ - в теореме Клини и двух принципиально разных подходах к реализации regex-движков.

• **grep, awk, sed:** классические Unix-утилиты используют Thompson NFA - мгновенный поиск в гигабайтных логах.
• **Cloudflare WAF (2019):** один «злой» regex уронил 50% глобального HTTP-трафика на 27 минут. ReDoS в продакшене - реальная угроза.
• **Компиляторы:** лексер (первый этап компиляции) строится как regex → NFA → DFA. Каждый раз, когда вы компилируете программу, теорема Клини работает на вас.

Теорема Клини: три лица регулярности

Какой самый мощный результат в теории регулярных языков? **Теорема Клини** утверждает, что три совершенно разных формализма описывают один и тот же класс языков:

Это означает, что если вы описали язык регулярным выражением - гарантированно существует DFA для него. И наоборот: для любого DFA можно записать regex.

**Почему это важно?** Вы выбираете самый удобный формализм для задачи. Хотите описать паттерн? Пишите regex. Хотите быстро проверять строки? Конвертируйте в DFA. Хотите доказать свойства? Работайте с автоматом. Всё это - один и тот же язык.

Доказательство теоремы состоит из **трёх конструктивных шагов** - каждый даёт конкретный алгоритм преобразования. Мы уже знаем NFA → DFA (subset construction). Осталось: Regex → NFA и DFA → Regex.

Алгоритм Томпсона: Regex → NFA

**Алгоритм Томпсона** (Ken Thompson, 1968) рекурсивно строит NFA из регулярного выражения. Идея: для каждой операции regex есть шаблон NFA-фрагмента. Фрагменты соединяются как детали конструктора.

Каждый NFA-фрагмент имеет ровно **один вход** и ровно **один выход**. Это позволяет легко комбинировать их.

**Свойство Томпсона:** NFA для regex длины n имеет не более **2n состояний** и **4n переходов**. Это линейно! Никакого экспоненциального взрыва на этом этапе.

Разберём конкретный пример: построим NFA для regex **(a|b)*c**

**На практике** ε-переходы можно частично устранить при построении: вместо двух состояний с ε-переходом - объединить их в одно. Это уменьшает число состояний, но усложняет код.

Обратное направление: DFA → Regex

Мы умеем Regex → NFA → DFA. А как получить regex из DFA? Метод **удаления состояний (State Elimination)** - самый наглядный способ.

Идея: поочерёдно удаляем промежуточные состояния, заменяя переходы на **регулярные выражения**. Когда останутся только начальное и конечное состояние - ребро между ними и есть искомый regex.

Разберём полный пример. DFA над {a, b}, принимающий строки с чётным числом символов 'a':

**Regex из state elimination может быть ОГРОМНЫМ.** Для DFA с n состояниями длина regex может расти как O(4ⁿ). Порядок удаления состояний влияет на размер результата - выбирайте «узлы-бутылочные горлышки» первыми.

Практика: движки regex и ReDoS

Теория говорит: regex → NFA → DFA, проверка строки длины m за O(m). Но на практике многие regex-движки работают **совсем иначе** - и это создаёт уязвимости.

Существует два принципиально разных подхода к реализации regex-движков:

Почему backtracking может быть катастрофически медленным? Рассмотрим regex **(a?){n}aⁿ** на строке **aⁿ** (n символов 'a'):

**ReDoS (Regular Expression Denial of Service)** - реальная атака. В 2016 году regex в модуле Node.js `ms` повесил серверы Stack Overflow. Уязвимые паттерны: вложенные квантификаторы (a+)+, перекрывающиеся альтернативы (a|a)+, комбинации .*.

Как защититься? Используйте движки на основе Thompson NFA:

**Почему backtracking-движки вообще существуют?** Потому что они поддерживают **backreferences** - например, `(a+)\1` (повторение захваченной группы). Это выходит за рамки регулярных языков! Проверка backreference - NP-полная задача. Thompson NFA не может этого по определению.

**Практический совет:** для валидации пользовательского ввода (email, URL) используйте проверенные библиотеки, а не самописные regex. Если пишете свой - тестируйте его на сайте regex101.com с длинными строками.

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

• **Теорема Клини:** DFA ⟺ NFA ⟺ Regex - три эквивалентных описания регулярных языков.
• **Thompson Construction:** Regex → NFA за линейное время (2n состояний для regex длины n).
• **State Elimination:** DFA → Regex через поочерёдное удаление состояний. Формула: R₁ · R* · R₂.
• **Backtracking vs Thompson NFA:** grep безопасен (O(nm)), Python/JS уязвимы (O(2ᵐ)). ReDoS - реальная атака.

Связанные темы

Теорема Клини связывает регулярные выражения, автоматы и формальные языки в единое целое:

• Конвертация NFA → DFA — Subset construction - среднее звено цепочки Regex → NFA → DFA
• Минимизация DFA — После конвертации DFA можно минимизировать для оптимальной работы

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

• Почему backreferences делают regex нерегулярным? Можете ли привести пример языка, который описывается regex с backreference, но не является регулярным?
• Если Thompson NFA гарантирует линейное время, почему все языки не перешли на него? Какие фичи regex были бы потеряны?
• Cloudflare WAF инцидент 2019 года затронул миллионы пользователей. Как бы вы проектировали систему, чтобы один regex не мог уронить весь сервис?

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

• fl-05-regex — Regex notation must be understood before converting it
• fl-07-nfa — Thompson construction targets NFA fragments
• fl-08-nfa-to-dfa — After Thompson construction, apply subset construction for DFA
• comp-09-lexer-generators — Lexer generators implement this exact pipeline