Автоматы

Определения

Автомат - это упорядоченная 5-ка вида $<A, S, S_0, D, M>$, где:

• $A$ - алфавит (просто множество символов), как правило, используется таблица ASCII
• $S$ - так называемое множество состояний, как правило, $S \subseteq {\mathbb N}$
• $S_0$ - начальное состояние, $S_0 \in S$
• $D$ - множество конечных состояний, $D \subseteq S$
• $M$ - самое интересное, матрица переходов: $M\colon S\times A \to S$

Конечный автомат - это такой автомат, в котором множества A и S конечны: $|A|, |S| \in {\mathbb N}$.

Детерминированный автомат - то же самое, что просто автомат.

Недетерминированный автомат - автомат, в котором матрица переходов имеет сигнатуру $M\colon S\times A \to 2^S$, а $S_0$ - множество, $S_0 \subseteq S$.

Семантика

Автомат - это такая штука, которая кушает ленту с записанными на ней символами и согласно этим символам изменяет некоторую внутреннюю переменную. Когда лента заканчивается, проверяется значение переменной. Считается, что если переменная оказалась в состоянии, принадлежащем множеству допускающих, автомат принял строку, в противном случае наоборот. Теперь более формально. Имеется переменная state, вначале имеющая значение $S_0$, и поток данных, в котором можно прочитать следующий символ при помощи некоторой функции, скажем, getchar (). Если поток данных неожиданно кончился, нужно проверить значение переменной state и напечатать результат. Иначе, заглянув в матрицу переходов, согласно ей изменить значение переменной state ($state := M(state, getchar ())$), после чего повторить всё сначала. Понятно, что в случае недетерминированного автомата переменная state - это множество (которое может быть представлено, скажем, списком), а изменение её значения - это map множества: $state' = \{x' \mid \exists x \in state\ x' \in M (x, getchar ())\}$.

$\varepsilon$-переходы

Автомат с $\varepsilon$-переходами - недетерминированный автомат, в алфавите которого есть выделенный символ $\varepsilon$, который никогда не встречается во входных данных, но, тем не менее, для него есть переходы в матрице $M$, при этом считается, что между любыми символами входного потока находится неограниченно много символов $\varepsilon$. Более формально:

Определим функцию получения всех возможных $\varepsilon$-переходов из множества состояний $A$:

${\mathrm M}_\varepsilon (A) = \bigcup_{x \in A} {\mathrm M}(x, \varepsilon)$

Тогда становится возможным определить функцию $\varepsilon$-переходов на любую глубину:

$\mathrm {Er} (X) = \bigcup_{i = 1}^{\infty} {\mathrm M}_{\varepsilon}^i (X)$

Откуда следующий переход равен:

$state' = \{x' \mid \exists x \in (state \bigcup \mathrm {Er} (state))\ x' \in M (x, getchar ())\}$

Проще говоря, $\varepsilon$-переходы позволяют делать переходы там, где обычно их делать нельзя.

Реализация

Конечный детерминированный

Проще всего автомат представить массивом шириной в количество символов и высотой в количество состояний, при этом считая, что алфавит - это ASCII, множество состояний - это числа от 0 до высоты автомата, а начальное состояние - 0. Конечные состояния поставляются отдельно :)

 let create_fsm n = (Array.create_matrix n 256 0, [])

После этого обработка такого автомата становится настолько очевидной, что я даже не буду приводить код.

Конечный недетерминированный

То же самое, что и детерминированный, только с заменой чисел на списки чисел, ну и в функции обработки придётся изменить нахождение следующего состояния на следующее множество состояний. Правда, тут возникает одна тонкость: простого List.map тут не хватит, надо ещё flatten'ом придавить, ну и одинаковые элементы убивать.

 let rec qsort = function
  |[] -> []
  |[x1] -> [x1]
  |x1::xs -> qsort (List.filter (fun x -> x < x1) xs) @ [x1] @
             qsort (List.filter (fun x -> x > x1) xs)
 
 let unite l = qsort (List.flatten l)
 
 let nextstates fsm curstates curchar =
  unite (List.map (fun x -> fsm.(x).(int_of_char curchar)) curstates)

Конечный недетерминированный с $\varepsilon$- переходами

А вот тут уже будет веселее. Во-первых, в наших автоматах сейчас просто нет места для $\varepsilon$-переходов - всё занято обычными. Поэтому я предлагаю увеличить количество столбцов до 257 и для $\varepsilon$ использовать последний. Кроме того, нужно сначала обработать все $\varepsilon$-переходы, а затем объединить их с обычными. Я предлагаю решить эту проблему следующим образом. Напишем отдельную функцию, которая будет производить переходы до тех пор, пока это не станет бессмысленно, то есть до тех пор, пока не будут найдены все доступные из данных состояний переходы. К сожалению, определение недетерминированных автоматов предлагает продолжать поиск до бесконечности, поэтому нужен критерий, показывающий, что больше ничего уже найдено быть не может. Моё предложение:

$E^n(X) \subseteq \bigcup_{i=1}^{n-1} E^i(X)$

То есть всё новое, что было найдено, на самом деле не новое, а хорошо забытое старое.

Теперь написание кода становится достаточно очевидным.

 let rec subset l1 l2 =
  match (l1, l2) with
    ([], _) -> true
   |(x1::_, []) -> false
   |(x1::_, y1::ys) when y1 < x1 -> subset l1 ys
   |(x1::_, y1::_) when x1 < y1 -> false
   |(_::xs, _::ys) -> subset xs ys
 
 let epsilon fsm states =
  let rec epsilon prevstates curstates =
   if (subset curstates prevstates) then prevstates else
   epsilon (qsort (prevstates @ curstates))
    (unite (List.map (fun x -> fsm.(x).(256)) curstates)) in
  epsilon [] states

Опять-таки, не стану приводить полный код применения автомата, ибо он очевиден.

Преобразование НКА в ДКА

Для начала заметим, что в каждый момент НКА характеризуется множеством своих состояний. Так как различных возможных множеств его состояний конечное число (не более чем $2^n$, где n - количество состояний), их можно пронумеровать. Кроме того, можно определить, содержится ли в данном множестве хотя бы одно конечное состояние, и если да, то, значит, можно считать всё множество конечным состоянием. Наконец, каждому множеству состояний и каждому символу соответствует единственное следующее множество состояний. Таким образом приходим к очевидному выводу: занумеровав все множества состояний НКА, построив матрицу с длиной, равной количеству этих множеств и ширины 256 и записав в каждую ячейку номер соответствующего состояния, получаем обыкновенный ДКА.

Правда, здесь нужно уточнить, что преобразование можно делать тупо, построив матрицу максимально возможной длины ($2^n$), просто сгенерировав всю булеану, а можно оставить только состояния, которые этот автомат может принимать, устроив ему пробный пробег, то есть построив дерево всех возможных случаев.

Кода не будет!

Регулярные выражения

Сначала несколько слов, почему я не выделил для регексов отдельную статью. Во-первых, они эквивалентны автоматам. Во-вторых, эти две темы так тесно переплелись в билетах, что в этой отдельной статье пришлось бы также упоминать про автоматы, а хотелось бы иметь всю информацию в одной статье.

Синтаксис

Проще всего описать синтаксис регексов при помощи грамматики:

<regex> ::= <regex><regex> // два выражения подряд
          | (<regex>) // ничего особенного, просто группировка
          | <regex>? // выражение 0 или 1 раз
          | <regex>* // выражение 0 или более раз
          | <regex>+ // выражение 1 или более раз
          | <regex>|<regex> // либо первое, либо второе, то есть xor
          | <char> // одна из букв латиницы или кириллицы в любом регистре, либо цифра
          | . // любой символ

Преобразование в НКА

Сначала вспомним, что такое автомат.

Автоматом называется двумерный массив списков чисел (состояний), т.е. int list array array, причём:

1. Количество строк не ограничено
2. Количество столбцов должно равняться 257
3. Числа неотрицательны
4. Числа строго меньше количества строк
5. Входным состоянием всегда является 0
6. Допускающее состояние всегда одно - номер последней строки
7. Все эпсилон-переходы находятся в 256-м столбце
8. Все прочие столбцы соответствуют символам таблицы ASCII

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

• Итак, автомат, эквивалентный регулярному выражению "." имеет всего 2 строки: нулевая полностью забита единицами, вторая пуста.
• Выражению вида "A", где A - любой символ, соответствует автомат, пустой за исключением единицы в нулевой строке на месте символа A.
• "(A)" эквивалентно "A".
• А вот регулярное выражение "AB" уже так просто не сдастся. Ему соответствует такой автомат: верхняя часть эквивалентна A, нижняя - B, и между ними налажен $\varepsilon$-переход из допускающего состояния A в начальное состояние B.
• Выражению "A|B" похоже на "AB": ему соответствует автомат, в котором также верхняя и нижняя части эквивалентны A и B, причём из начального состояния A имеется $\varepsilon$-переход в начальное состояние B, а из допускающего состояния A - в конечное состояние B. Таким образом получается что-то вроде параллельного выполнения.
• "A?" эквивалентен автомат, имеющий $\varepsilon$-переход из начального состояния в конечное.
• "A+" порождает автомат, имеющий $\varepsilon$-переход из конечного состояния в начальное.
• И наконец, "A*" - это автомат, в котором имеется $\varepsilon$-переход как из начального состояния в конечное, так и наоборот.

Построение по НКА

Утверждение номер раз. С НКА возиться долго и муторно, поэтому, как объяснено выше, преобразуем НКА в ДКА и расслабимся.

Утверждение номер два. Существуют два различных способа преобразования ДКА в регулярное выражение: первый - сложный и математический, второй - простой и человеческий. Начнём с первого.

Рассмотрим следующую штуку: ${\mathbb W}_{i\,j}^k$ - множество подстрок, разбор которых начинается в состоянии $i$ и заканчивается в состоянии $j$, причём номера состояний в промежутке между начальным и конечным не превышают $k$. Заметим, что $\bigcup_{d_i \in D} {\mathbb W}_{0\,d_i}^{n-1}$ - все возможные слова. Нетрудно понять, что если уметь преобразовывать каждый из элементов объединения в регекс, то регулярным выражением, эквивалентным автомату, будет что-то вроде ${\mathrm R}_{0\,d_0}^{n-1} | {\mathrm R}_{0\,d_1}^{n-1} | \dots | {\mathrm R}_{0\,d_{k-1}}^{n-1}$, где ${\mathrm R_{i\,j}^k}$ - это регулярное выражение, соответствующее ${\mathbb W}_{i\,j}^k$. Таким образом, надо научиться строить регулярные выражения для таких элементов. Будем доказывать, что это возможно, по индукции.

${\mathbb W}_{i\,j}^k \to\ {\mathrm R_{i\,j}^k}$ (индукция по $k$)

Для начала введём некоторые вспомогательные функции.

${\mathrm P} (i, j) = \{a \mid {\mathrm M} (i, a) = j\}$ - все символы, вызывающие переход из состояния i в состояние j

${\mathrm R} (i, j) = {\mathrm P} (i, j) = {\mathrm P}_0 \mid {\mathrm P}_1 \mid \dots \mid {\mathrm P}_{l-1}$ - и регекс, соответствующий этим символам

База ($k=0$):

${\mathbb W}_{i\,j}^0 \Rightarrow {\mathrm R}_{i\,j}^0 = {\mathrm R}(i, j) \mid ({\mathrm R}(i, 0)) ({\mathrm R}(0, 0))^{*} ({\mathrm R}(0, j))$

Переход:

${\mathbb W}_{i\,j}^{k+1} \Rightarrow {\mathrm R}_{i\,j}^{k+1} = {\mathrm R}_{i\,j}^k \mid {\mathrm R}_{i\,(k+1)}^k ({\mathrm R}_{(k+1)\,(k+1)}^k)^{*} {\mathrm R}_{(k+1)\,j}^k$

Короче говоря, здесь надо просто сесть и подумать.

Второй алгоритм можно назвать "vertex elimination". Суть его состоит в том, что автомат представляется в виде графа, у которого последовательно уничтожаются все вершины, кроме начального и конечного состояний, а ссылки на уничтоженные вершины перенаправляются, делаются "сквозными". К сожалению, пример привести довольно сложно в связи с ограниченностью средств редактирования, а без него я не имею ни малейшего понятия, как этот алгоритм можно объяснить.