Источник: http://www.rsdn.ru/article/alg/nka.xml

Недетерминированные конечные автоматы

Автор: Сергей Холодилов
The RSDN Group
Источник: RSDN Magazine #2-2007

Опубликовано: 30.07.2007
Исправлено: 15.04.2009
Версия текста: 1.0

Просто конечные автоматы
Добавляем недетерминированность

Подход №1
Подход №2
Подход №3

… и эпсилон-переходы

… и более формально

И почему это круто
Реализация методом «в лоб»

Производительность
ε-переходы

Реализация преобразованием в ДКА

Теория
Алгоритм
Код
Производительность

Заключение

Подвёл ты меня, Боролгин. А ведь я все деньги на тебя поставил. 
.. <тут Боролгин сокрушается> ..
Не горюй, Боролгин. Я ещё и на орков поставил.

Арагорн в переводе Гоблина

Недетерминированные конечные автоматы – одна из моделей, используемых в теории вычислений. Вряд ли всё это когда-нибудь пригодится вам «по жизни»… но, чёрт возьми, математика – это интересно! Во всяком случае, для меня. А если уж она хоть как-то с программированием связана, то интересна вдвойне.

Я не претендую на математическую строгость, получилось что-то типа «популярной математики для чайников»… Но надо же с чего-то начинать. А причём здесь орки – поймёте по ходу дела :)

Просто конечные автоматы

Скорее всего, все более-менее знают, что такое конечные автоматы. Проблема в том, что я, например, знаю три варианта: конечные автоматы Мура, конечные автоматы Мили и «просто» конечные автоматы. Поскольку дальше нам потребуется вполне конкретное определение, имеет смысл ввести его здесь.

Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:

Q – конечное множество состояний.
Σ – конечное множество входных символов.
δ – функция перехода. Аргументы – состояние и входной символ, результат – состояние.
q₀ – начальное состояние, принадлежит Q.
F – множество допускающих состояний, является подмножеством Q.

И функционирующие следующим образом:

Автомат начинает работу в состоянии q₀.
Если автомат находится в состоянии q_i, а на вход поступает символ b, то автомат переходит в состояние δ(q_i, b).

ПРИМЕЧАНИЕ

Возможно, более простым вам покажется следующее определение: детерминированным конечным автоматом называется такой автомат, в котором при любой данной последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. – прим.ред.

Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.

ПРИМЕЧАНИЕ

Это определение конечного автомата используется в теории вычислений. Автоматы Мура и Мили используются, в основном, при проектировании цифровой аппаратуры.

Конечные автоматы удобно изображать графически. На рисунке 1 приведён несложный ДКА, допускающий цепочки из 0 и 1, заканчивающиеся символом 0. Начальное состояние помечено входящей в него стрелочкой (да, этот здоровенный треугольник в душе – стрелочка), допускающее (в данном случае оно одно) – двойным кружком.

Рисунок 1. Простой детерминированный конечный автомат.

Второй вариант изображения автоматов – таблица переходов.

		0	1
->	q₀	q₁	q₀
*	q₁	q₁	q₀

Таблица 1. Тот же самый конечный автомат.

По горизонтали отложены символы входного алфавита, по вертикали – состояния, начальное состояние отмечено стрелочкой, а допускающие – звёздочками. Этот способ изображения менее нагляден, и приведён только в качестве примера, использовать его «для дела» я не буду.

Добавляем недетерминированность

Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:

δ – функция перехода. Аргументы – состояние и входной символ, результат – множество состояний (возможно – пустое).
Если автомат находится в состоянии q_i, а на вход поступает символ b, то автомат переходит во множество состояний δ(q_i, b). Если автомат находится во множестве состояний {q_i}, то он переходит во множество состояний, получаемое объединением множеств δ(q_i, b).

НКА тоже распознаёт цепочки символов, цепочка считается допустимой, если после её обработки множество состояний, в котором оказался автомат, содержит хотя бы одно допускающее. Таким образом, НКА также задаёт некоторый язык.

На рисунке 2 изображён простой НКА, допускающий цепочки из 0 и 1, заканчивающиеся на 00.

Рисунок 2. Простой недетерминированный конечный автомат.

Этот же автомат в виде таблицы:

		0	1
->	q₀	{q₀, q₁}	{q₀}
	q₁	{q₂}	Ø
*	q₂	Ø	Ø

Таблица 2. Тот же самый недетерминированный конечный автомат.

Разберёмся, как он работает.

Подход №1

Допустим, на вход автомату поступила цепочка «100100».

До	Вход	Описание	После
		Автомат начинает работу в множестве состояний {q₀}	{q₀}
{q₀}	1	Из состояния q₀ по символу 1 существует только один переход, в q₀ же.	{q₀}
{q₀}	0	Из состояния q₀ по символу 0 существует два перехода, в q₀ и в q₁.	{q₀, q₁}
{q₀, q₁}	0	Из состояния q₀ по символу 0 существует два перехода, в q₀ и в q₁, из состояния q1 – один переход, в q₂. Поскольку автомат находится в двух состояниях, множества объединяются.	{q₀, q₁, q₂}
{q₀, q₁, q₂}	1	Автомат находится в трёх состояниях, но из q₁ и из q₂ не существует переходов по символу 1 (т.е. значение функции перехода из этих состояний по входному символу 1 – пустое множество). В итоге остаётся только q₀.	{q₀}
{q₀}	0	И т.д.	{q₀, q₁}
{q₀, q₁}	0	И т.п. Так как в получившемся множестве состояний есть q₂ – допускающее состояние, автомат признаёт цепочку корректной.	{q₀, q₁, q₂}

Таблица 3. Обработка цепочки 100100.

Продолжение статьи на http://www.rsdn.ru/article/alg/nka.xml