Автоматы

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

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

A – конечное множество, называемое алфавитом
S – конечное множество, называемое множеством состояний
элемент s0 множества S, называемый начальным состоянием
t: A x S -> S – отображение, называемое функцией переходов

Для любой конечной последовательности букв (так мы будем называть элементы A) a(0), a(1), … a(n) можно рассмотреть последовательность состояний автомата s(0), s(1), … s(n+1), заданную соотношениями

s(0) = s0
s(k+1) = t(a(k),s(k))

На практике часто встречаются автоматы, снабжённые дополнительно функцией значений v: A x S -> V. Например, типичная схема управления лифтом наиболее естественно представляется как раз в виде такого автомата, где элементы A – сигналы, поступающие от датчиков, а элементы V – сигналы, подаваемые на моторы дверей или лебёдки.

Что касается программирования, то таким образом, например, был реализован ввод-вывод в чистых функциональных языках на заре их появления, до прихода туда CPS, монад и прочих нетривиальных механизмов. Сейчас ровно такой же подход очень популярен в веб-разработке (см. Elm, React, Redux и т.п.).

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

Недетерминированные конечные автоматы (НДКА) в настоящий момент – наиболее часто используемый способ поиска по тексту. Правда, среднестатистическому программисту они больше известны под названием регулярные выражения (РВ). Что такое РВ, и как они устроены, мы обсудим в конце этой главы. А пока введём стандартное представление НДКА:

алфавит A
состояния S
начальное подмножество состояний p0
функция переходов t: A x S -> PS

Текст a(0), a(1), … a(n) порождает последовательность подмножеств p(0), p(1), … p(n+1), заданную соотношениями:

p(0) = p0
p(n+1) = объединение по всем s из p(n) подмножеств t(a(n),s)

Посмотрев на последнее равенство, легко заметить, что по функции t можно построить функцию T: A x PS -> PS, для которой

p(n+1) = T(a(n),p(n))

Поэтому любой НДКА эквивалентен ДКА, множеством состояний которого является множество всех подмножеств множества состояний НДКА.

НДКА для поиска подтекста

Наверное, одним из наиболее важных НДКА являются автоматы, предназначенные для поиска подтекста внутри текста. Строятся такие НДКА тривиально: предположим, что нам нужно найти последовательность abba. Рассмотрим следующий автомат с состояниями 0, 1, 2, 3, 4:

s0 = 0

t(a,0) = {0,1}
t(b,0) = {0}
t(a,1) = {}
t(b,1) = {2}
t(a,2) = {}
t(b,2) = {3}
t(a,3) = {4}
t(b,3) = {}

Заметим, что последовательность abba есть во входном тексте тогда и только тогда, когда в какой-то момент состояние 4 оказалось в текущем подмножестве состояний.

К сожалению, наивная реализация подобных автоматов ничуть не эффективнее сравнения искомого подтекста со всеми подтекстами входного текста: если мы ищем подтекст длины M внутри текста длины N, то для того, чтобы обработать один шаг автомата, нам потребуется в худшем случае вычислить и объединить (M+1) множество. Суммарное количество операций, соответственно, пропорционально MN.

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

Более того, можно предварительно перевести автомат в каждое из возможных состояний и подать все возможные буквы. Полученный ДКА дальше можно применять к любому тексту.

Автомат Кнута-Морриса-Пратта

В конце прошлого раздела сложность поиска подтекста в тексте мы снизили с MN до N + |A|M^2 (верхняя оценка как на количество наивных переходов, так и на сложность каждого из них пропорциональна M).

Тем не менее, эту оценку можно ещё улучшить. Оказывается, соответствующий ДКА имеет простое индуктивное описание.

Построим автомат для поиска подтекста b(0), b(1) … b(n). Пусть T – функция переходов для автомата, построенного по b(0) … b(n-1). Рассмотрим следующий НДКА:

p0 = { 0 }

t(x,0) = { T(x,0) }
...
t(x,n-1) = { T(x,n-1) }

t(x,n)    = { T(x,n) }, если x не b(n)
t(b(n),n) = { T(b(n),n), n+1 }
t(x,n+1)  = {}

Про него очевидно три вещи:

он нашёл подтекст тогда и только тогда, когда находится в «состоянии» { n+1, ... }
это – единственное «состояние», состоящее из более чем одного состояния
оно устроено так: { n+1, T(b(n),n) }

Поэтому в ДКА, соответствующем нашему НДКА, переходы (отличные от T(x,k)) задаются формулами:

t(b(n),n) = n+1
t(x,n+1)  = t(x,T(b(n),n))

Этот автомат (точнее, этот способ его построения) называется автоматом Кнута-Морриса-Пратта. Верхняя оценка на сложность построения пропорциональна |A|M.