Автоматы и сознание

Конечные автоматы - язык состояний

Цели урока

  • Понимать что FSM = состояния + входы + переходы, и где это применяется
  • Знать формальное определение DFA (Q, Σ, δ, q₀, F) и эквивалентность NFA/DFA
  • Видеть связь регулярных выражений с FSM по теореме Клини
  • Распознавать опасные паттерны regex (ReDoS) и понимать как защититься

Предварительные знания

  • Базовое понимание множеств и функций
  • Базовый опыт программирования (любой язык)
  • Желательно: интуиция про регулярные выражения

TCP-соединение - это FSM. Регулярки - это FSM. NPC в Doom - это FSM. Лифт - это FSM. Один концепт 1943 года (Маккаллок-Питтс) до сих пор лежит в основе цифрового мира.

  • **TCP/IP стек (RFC 793, 1981)** - 11 состояний на каждое соединение, диаграмма не менялась 44 года
  • **Cloudflare ReDoS (2019)** - один regex с вложенным квантификатором положил 1.1.1.1 на 27 минут
  • **Doom (1993)** - все враги работают через FSM с состояниями patrol/chase/attack/flee
  • **Stack Overflow (2016)** - 34 минуты простоя из-за regex с экспоненциальным backtracking
  • **React state machines (XState)** - современная библиотека для UI-компонентов на основе FSM

Маккаллок и Питтс - первая модель искусственного нейрона

В 1943 году нейрофизиолог Маккаллок и логик Питтс опубликовали "A Logical Calculus of Ideas Immanent in Nervous Activity" - первую формальную модель нейрона как логического элемента. Из этой статьи выросли две ветки: 1. формальные грамматики и теория автоматов через Клини и Хомского 2. искусственные нейронные сети через Розенблатта (perceptron 1958) и Хинтона (deep learning 2006). Один документ - корень и FSM, и современного ИИ.

Что такое конечный автомат

**Каждый раз когда открывается страница сайта, происходит TCP handshake. И каждое TCP-соединение - это конечный автомат с 11 состояниями: CLOSED → LISTEN → SYN_SENT → SYN_RECEIVED → ESTABLISHED → FIN_WAIT_1 → ... В RFC 793 (1981) этот автомат прорисован как диаграмма - и за 44 года ничего не изменилось.** Конечные автоматы - не академическая абстракция. Это базовый язык, на котором написана инфраструктура цифрового мира.

**Конечный автомат (Finite State Machine, FSM)** - модель поведения с 4 компонентами: 1. конечное число **состояний** 2. **алфавит входов** (что может прийти) 3. **функция переходов** (на какой вход - в какое состояние) 4. **начальное состояние**. Никакой памяти кроме текущего состояния.

Где работают FSM прямо сейчас

ГдеСостоянияМасштаб
TCP/IP стек11 состояний на соединение~10^10 активных соединений в мире
Регулярные выражения (NFA/DFA)Зависит от паттернаПарсинг трафика, валидация форм - миллиарды раз в секунду
Лексеры компиляторовСостояния для чисел/строк/идентификаторовКаждая компиляция любой программы
NPC в играх (Doom 1993, GTA V)Patrol → Chase → Attack → FleeМиллионы игровых сессий
Vending machines, банкоматы, лифтыIdle → Selecting → DispensingФизический мир
UI-компоненты (React state)Loading → Success → ErrorКаждое веб-приложение

Простой пример - турникет в метро

**2 состояния, 2 входа (`card`, `push`), 4 перехода.** Турникет не знает сколько раз через него прошли, кто прошёл, в какое время. Только текущее состояние и реакция на следующий вход. Это и есть суть FSM - **полное поведение системы определяется текущим состоянием**, история не нужна.

FSM - это просто куча `if/else` в коде

FSM - это явная модель, где состояния и переходы видны и формально проверяемы

Куча `if/else` обычно тянет за собой неявное состояние через десятки флагов и переменных - тестировать сложно, ошибок легион. FSM делает все возможные состояния явными. Можно нарисовать диаграмму, доказать корректность, найти недостижимые состояния. TLA+ и SPIN автоматически проверяют такие модели на свойства типа "турникет никогда не пропустит без оплаты".

Что отличает FSM от обычной программы с переменными?

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

**Формально DFA (Deterministic Finite Automaton) - это пятёрка** `M = (Q, Σ, δ, q₀, F)`:

  • **Q** - конечное множество состояний (например `{LOCKED, UNLOCKED}`)
  • **Σ** - входной алфавит (`{card, push}`)
  • **δ: Q × Σ → Q** - функция переходов (даёт новое состояние по текущему + входу)
  • **q₀ ∈ Q** - начальное состояние (`LOCKED`)
  • **F ⊆ Q** - множество принимающих состояний (для распознавателей строк)

**DFA (детерминированный)**: на каждый вход в каждом состоянии - ровно один переход. **NFA (недетерминированный)**: на один вход может быть 0, 1 или несколько переходов одновременно. NFA удобнее проектировать, DFA быстрее исполнять. Знаменитая теорема Рабина-Скотта (1959) доказывает что любой NFA можно превратить в эквивалентный DFA - правда с экспоненциальным взрывом числа состояний в худшем случае.

Пример: распознать строки заканчивающиеся на 'ab'

**Цена детерминизма:** при превращении NFA → DFA число состояний может вырасти как 2^n. Поэтому реальные движки регулярных выражений (Go regexp, RE2 от Google) используют NFA напрямую с симуляцией всех возможных состояний параллельно - O(n×m) гарантировано вместо экспоненциального взрыва PCRE.

NFA мощнее DFA - может распознать больше языков

NFA и DFA эквивалентны по выразительной силе - распознают точно один и тот же класс языков (регулярные)

Это знаменитый результат Рабина-Скотта 1959 года, за который они получили Turing Award в 1976. NFA удобнее писать и часто компактнее, но любой NFA конвертируется в DFA (subset construction). Истинное расширение силы даёт только добавление памяти - стек (PDA = pushdown automaton) или ленту (Turing machine).

DFA с 10 состояниями превращён в эквивалентный NFA. Сколько состояний может иметь NFA в наилучшем случае?

Регулярные выражения - это FSM

**Когда пишется `/^[a-z]+@[a-z]+\.[a-z]+$/` - под капотом строится FSM.** Каждый символ в регэксе превращается в состояния и переходы по теореме Клини (1956). Это самое массовое практическое применение FSM в индустрии: каждая валидация формы, каждый grep, каждый парсер логов.

Соответствие операторов и FSM-конструкций

RegexFSM-конструкцияПример
`a`Один переход по символу 'a'q0 --a--> q1
`a|b`Альтернатива - два пути из одного состоянияИз q0 либо a, либо b
`a*`Цикл с возможностью пропуститьq0 --a--> q0 (петля)
`ab`Конкатенация - последовательные переходыq0 --a--> q1 --b--> q2
`a+`Один или больше = a · a*Минимум один переход + петля
`[a-z]`Один переход с большим алфавитом26 параллельных переходов

Знаменитый случай ReDoS

**Cloudflare, 2 июля 2019. 13:42 UTC. Один новый regex в WAF-правиле кладёт CPU всех серверов до 100% за 10 минут. Сайт 1.1.1.1 (DNS) недоступен 27 минут.** Причина - паттерн `(?:(?:"|'|\]|\}|\\|\d|...|\?)+)+` создал NFA, в котором один вход порождает экспоненциальное число одновременных путей. Это ReDoS - Regular Expression Denial of Service.

**Защита от ReDoS:** 1. использовать движки на NFA-симуляции - RE2 (Google), Rust regex, Go regexp. 2. запрещать вложенные квантификаторы в user-input regex. 3. ставить timeout на исполнение паттерна. Stack Overflow в 2016 лежал 34 минуты из-за такого regex - публичный postmortem стоит прочесть.

Главное из урока

  • FSM = состояния + входы + переходы. Полное поведение определяется текущим состоянием
  • FSM везде: TCP, regex, lexers, NPC, UI - один и тот же аппарат
  • DFA (один переход на вход) и NFA (несколько) эквивалентны по выразительности (Рабин-Скотт 1959)
  • Регулярные выражения = NFA по теореме Клини (1956). Все движки строят FSM под капотом
  • Без памяти FSM не может считать. Чтобы посчитать `aⁿbⁿ` нужен PDA (стек), а для произвольных языков - Turing machine

Дальше в курсе

От простых FSM к моделям с памятью и вероятностью.

  • Цепи Маркова — FSM с вероятностями переходов - модели текста, рекомендации, PageRank
  • Скрытые марковские модели (HMM)

Ключевые понятия

  • FSM - это пятёрка (Q, Σ, δ, q₀, F): состояния, алфавит, функция переходов, начальное состояние, принимающие состояния
  • Полное поведение FSM определяется только текущим состоянием - история не нужна
  • DFA: на каждый вход - ровно один переход. NFA: на один вход возможны несколько переходов одновременно
  • DFA и NFA эквивалентны по выразительной силе (теорема Рабина-Скотта, 1959) - распознают один и тот же класс регулярных языков
  • Регулярные выражения = FSM по теореме Клини (1956): каждый паттерн компилируется в граф состояний
  • ReDoS - атака на движки с backtracking: вложенные квантификаторы создают экспоненциальное число путей. Защита - RE2, Go regexp (NFA-симуляция, O(n))

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

  • Подумай о приложении которым пользуешься ежедневно. Какие state machines в нём явно работают (loading-states, формы, навигация), а какие неявно (auth-flow, online/offline переходы)?

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

  • fl-01-intro — Регулярные языки - это ровно то, что распознают конечные автоматы
  • aut-02-markov-chains — Цепи Маркова - вероятностное расширение FSM с переходами по вероятностям
  • nlp-01 — Токенизаторы (tiktoken) - это DFA над Unicode; FSM в основе обработки текста
  • comp-01 — Машина Тьюринга - расширение конечного автомата с бесконечной лентой памяти
  • fl-06-dfa
Конечные автоматы - язык состояний

0

1

Войти

— Вероятности + скрытые состояния - распознавание речи, биоинформатика
  • MDP и обучение с подкреплением — FSM с действиями и наградами - база reinforcement learning
  • Pushdown automata — FSM + стек = парсинг контекстно-свободных языков (синтаксис языков программирования)

    • Почему `(a+)+` опасный паттерн в большинстве regex-движков?