Конечные автоматы: состояния, переходы и регулярные языки

Турникет в метро не помнит, кто вы и сколько раз вы сегодня ездили. Он помнит ровно одно: открыт он сейчас или закрыт. Монетка — переходит в состояние «открыт», проход — возвращается в «закрыт». Всё. И при этом конструкция решает задачу доступа идеально. Конечный автомат — модель систем, которым хватает конечной памяти: турникеты, контроллеры лифтов, парсеры, сетевые протоколы. Это финальная тема курса, и она красиво замыкает всё, что мы уже изучили: состояния и переходы — это граф, условия переходов — логика, а сам автомат — способ определять язык.

Формальная модель: пять штук в скобках#

Детерминированный конечный автомат (ДКА) — пятёрка $(Q,\Sigma ,\delta ,q_0,F)$:

• $Q$ — конечное множество состояний (для турникета: «закрыт», «открыт»)
• $\Sigma$ — входной алфавит: символы, которые автомат читает (монетка, проход)
• $\delta :Q\times \Sigma \to Q$ — функция переходов: из какого состояния и по какому символу — куда идём
• $q_0\in Q$ — начальное состояние, здесь автомат живёт до первого символа
• $F\subseteq Q$ — множество допускающих (принимающих) состояний

Работает автомат так: читает входное слово символ за символом и шагает по переходам. Слово допускается, если после последнего символа автомат оказался в состоянии из $F$. Множество всех допускаемых слов — язык автомата. Никакой памяти, кроме текущего состояния, у автомата нет — в этом и сила модели, и её предел.

Рисуют автомат диаграммой состояний: состояния — кружки, переходы — стрелки с подписями символов, старт отмечают входящей стрелкой, допускающие состояния — двойными кружками. По сути, это ориентированный граф с помеченными рёбрами — техника из основ графов напрямую переносится сюда. Вторая форма записи — таблица переходов: строки-состояния, столбцы-символы, в клетке куда идём; по структуре это матрица переходов.

Первый пример: чётность единиц#

Задача: допускать двоичные слова с чётным числом единиц. Состояний нужно два: $E$ («прочитано чётное число единиц») и $O$ («нечётное»). Ноль единиц — число чётное, значит старт в $E$, и $F=\{E\}$. Переходы: по 0 состояние не меняется, по 1 — переключается между $E$ и $O$.

Трассируем слово $1011$: старт в $E$; символ 1 — идём в $O$; символ 0 — остаёмся в $O$; символ 1 — в $E$; символ 1 — в $O$. Конец слова, автомат в $O$ — слово не допускается. Проверка руками: в $1011$ три единицы — нечётно, верно. Механика железобетонная: состояние просто «помнит» чётность прочитанного, и никакой счётчик не нужен.

1. 1
   Условие: допускать двоичные слова, в которых никогда не встречаются две единицы подряд.
2. 2
   Что помнить? Только чем кончилось прочитанное: $q_0$ — «кончилось нулём или пусто», $q_1$ — «кончилось единицей».
3. 3
   Третья состояние-ловушка $q_2$ — «уже видели 11»: из неё выходов нет, любое продолжение остаётся в ней.
4. 4
   Переходы: из $q_0$ по 0 — в $q_0$, по 1 — в $q_1$; из $q_1$ по 0 — в $q_0$, по 1 — в ловушку $q_2$; из $q_2$ по любому символу — в $q_2$.
5. 5
   Допускающие: $q_0$ и $q_1$. Трасса слова 10101: $q_0{\to }^1{q}_1{\to }^0{q}_0{\to }^1{q}_1{\to }^0{q}_0{\to }^1{q}_1$ — допускается. Слово 1101 после второй единицы уходит в $q_2$ и остаётся там — не допускается.

Проектируем автомат по шагам#

Типовая задача семинара: построить автомат для заданного условия. Алгоритм такой: придумать, какую информацию о прочитанной части слова нужно помнить (это и будут состояния), определить переходы для каждого символа из каждого состояния, пометить допускающие, прогнать несколько тестовых слов. Разберём: допускать слова над алфавитом $\{a,b\}$, которые оканчиваются на $ab$.

ДКА против НКА: детерминизм#

В недетерминированном автомате (НКА) переход может вести сразу в несколько состояний, а некоторые переходы разрешено помечать пустым словом $\epsilon$ (читать символ не нужно). Слово допускается, если существует хотя бы один путь по переходам, приводящий в допускающее состояние. Формально функция переходов превращается в отображение $Q\times \Sigma \to 2^Q$ — в множество состояний.

НКА кажется мощнее: он как будто «угадывает» правильную ветку. Теорема Рабина-Скотта утверждает: нет. Любой НКА можно детерминизировать построением ДКА, состояния которого — подмножества состояний НКА (в худшем случае их $2^{|Q|}$, но на практике обычно меньше). Оба класса распознают в точности одни и те же языки. НКА удобнее конструировать, ДКА — исполнять: поэтому реальные инструменты хранят НКА-подобные структуры, а исполняют детерминизированную версию.

Мини-пример детерминизации можно устроить в уме. Пусть НКА по символу a из состояния $p$ идёт сразу в $p$ и $q$. Соответствующий ДКА будет иметь состояние-подмножество $\{p,q\}$ и переход $\{p,q\}{\to }^a\{p,q,\dots \}$ — объединение образов. Смотрите, как растёт счёт: два состояния НКА породили до четырёх состояний ДКА; десять — до 1024. Отсюда практический совет: конструируйте НКА, детерминизируйте только те подмножества, которые реально достижимы со старта — обычно их на порядки меньше $2^{|Q|}$.

Регулярные языки и где это всё живёт#

Языки, распознаваемые конечными автоматами, называются регулярными. Теорема Клини связывает их с регулярными выражениями: классы совпадают. Каждое регулярное выражение можно скомпилировать в НКА (алгоритм Томпсона), детерминизировать, минимизировать — и исполнять с линейной скоростью. Именно так работает grep, движки регулярных выражений и лексический анализатор компилятора: автомат читает исходный код посимвольно и нарезает его на токены.

Предел модели стоит знать: память автомата конечна, поэтому «посчитать» он не может ничего. Язык «равное число открывающих и закрывающих скобок» автомату не по силам — нужен счётчик неограниченной длины (для этого существуют стековые автоматы, на которых построены парсеры). Практическое следствие: валидацию форматов (телефоны, почтовые индексы) делают автоматами, а разбор вложенных конструкций — нет.

• Состояния — это вся память; проектирование начинается с вопроса «что помнить о прочитанном».
• ДКА: из каждого состояния по каждому символу ровно один переход — не хватает варианта, добавляйте ловушку.
• НКА: переходы в множества и $\epsilon$-шаги; слово допускается, если существует хотя бы один успешный путь.
• Детерминизация растит состояния до $2^{|Q|}$, минимизация сжимает обратно.
• Считать автомат не умеет: вложенные скобки и произвольные палиндромы — не его язык.