Конечные автоматы

Blog by admin

Введение

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

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

Детерминированный кончечный автомат (ДКА)

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

В данном автомате состояние — это остаток текущего считанного числа на 3.
Желтые вершины — это терминальные состояние. Если по окончанию приема строки автомат оказался в одном из таких состояний, то это слово ДКА принимает.
Автомат задается пятью параметрами:

Σ — алфавит на котором автомат работает
Q — множество состояний автомата
F — множество терминальных состояний
q₀ — начальное состояние
δ — функия преходов автомата (δ: Q x Σ -> q ∈ Q)

Из любого состояние должен быть только один преход по символову, иначе этот автомат недерминирован.
ДКА является самым удобным из всех конченых автоматов. Его удобнее всего обработаывать, всегда стараются свести задачу к построению ДКА. Но разобрать НКА и ε-НКА также необходимо.

Недетерминированный конечный автомат(НКА)

Предположим нам надо построить автомат, который принимает все строки, состоящие из символов [0, 1], где второй символ будет 0.

У нас возникла трудность в том, что из вершины Q₀ у нас два прехода по символу 0. Это отличительная особенность НКА от ДКА:
δ — функия преходов автомата (δ: Q x Σ -> P(Q)), где P(Q) — это подмножество состояний Q.
Теперь по одному символу можно перейти в несколько состояний.

ε-Недетерминированный конечный автомат (ε-НКА)

ε-НКА очень похож на НКА, только теперь мы можем преходить по ε. Теперь ничего не считав, мы сможем перейти из одной вершины в другую.

Принмает теже слова, что и предыдущий

Эквиалетность

Есть свойство у конченых автоматов — это их эквиалетность. ДКА <=> НКА <=> ε-НКА. Благодаря этому мы можем спокойно из ε-НКА сделать ДКА, это нам сильно пригодится.

Вкратце, разобрав какие бывают автоматы, мы можем перейти к более подробному изучению их реализации

Реализация

Обработка автомата

Как же можно проверить принимает ли данный кончечный автомат строку.
Для ДКА все очевидно. Мы храним матрицу преходов, текущее состояние (когда мы ничего не считали, тек. сотояние = начальное состояние) и терминальные вершины. Считываем по одному символу, и переходим в состояние по матрице перехода.

Для НКА вместо текущего состояния мы храним множество текущих состояний. Разберем НКА данный выше.

Пусть мы хотим перейти по символу 0. Текущее множество состояний — множество, состоящее из одной вершины — начальной. У нас есть два прехода по символу 0 => множество состояний у нас будет {Q₀, Q₁}. Затем перейдем по символу 0. Из Q₀ мы попадаем в Q₀ и в Q₁, из Q₁ в Q₂ => наше множество будет {q₀, q₁, q₂}.

Обработка ε-НКА похожа на обработку НКА. Предположим наше текущее множество S. Перед считываением следущего символа: для всех q ∈ S добавить в множество S вершину достигаемую из q по символу ε.

Детерминация автомата

Перевести автомат из ДКА в НКА легко. Нам просто ничего не нужно делать, т.к. ДКА это обобщенный случай НКА.
Но что делать если мы хотим превести из ε-НКА в ДКА (НКА является обобшенным случаем ε-НКА). Этот процесс называется детерминацией автомата.

Начнем обоходить наш ε-НКА, например, DFS-ом. Вершиной графа является множество текущих состояний. Состояниями нового ДКА будут все вершины графа. При переходе к новой веришне мы выбираем символ по которому хотим перейти, и добавляем этот переход. Приведу псевдокод DFS-a для большой ясности:

<pre>
DFS(set v)
{
        for c ∈ Σ
        {
                set tmp = множество состояний получаемых из множества v преходя по символу с;
                addDKA(v, tmp, c) - добавляем в наш ДКА состояние tmp, и добавляем переход из v по символу c в состояние tmp;
                DFS(tmp);
        }
}
</pre>

Если в множестве есть терминальное состояние, то состояние нового ДКА будет тоже терминальным.

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

Алгоритм минимизации ДКА

Любой ДКА имеет эквиалетный ему ДКА с минимальным числом состояний. Как его «сжать»? Заметим, что неразличимые вершины мы можем соединить в одну.
Что такое различимое состояние?
Состояние p и q являются различимыми, если есть такое слово s, что преходя из вершины p по слову s мы попадаем в терминальное состояние, а из вершины q в не-терминальное, или наоборот.

1) Терминальное и не-терминальное состояние являются различимыми. Перейдем по пустому слову и окажемся в двух различимых состояниях.
2) Состояния a и b различимы. Если существуют состояния c и d, и из c есть переход по символу x в состояние a, а из веришны d есть переход по символу x в состояние b, то состояние a и b различимы.

Мы нашли все различимые состояния. Теперь нам надо «схлопнуть» все неразличимые.

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

Регулярные варжения напрямую связаны с конечными автоматами. Введем некоторые обозначения:
∅ — пустое множество.
ε — строка, которая не сожержит символов.

Пусть A и B регулярные выражения. L(A) и L(B) — кончечные языки, которые данные регулярные варжения задают.

A|B <=> L(A) ∪ L(B)
AB <=> {xy}, x ∈ L(A), y ∈ L(B)
A* <=> {x₁x₂...x_n} n>=0, ∀ x ∈ L(A) (замыкание Клини)
Операции данные в порядке возврастания приоритета.

Это основные операции прменимые к регулярным варжением. Можно всетрить и другие, но все они могут быть представлены операциями данными выше.

ДКА -> Регулярное выражение

Научимся получать из ДКА регулярное выражение. Воспользуемся методом динамического програмирования.
R_i,j,k — это регулярное выражение, которое описывает все слова, переводящие автомат из состояния i в состояние j через состояние <=k.

При k = 0

Если i != j R_i,j,k = x₁|x₂|..|x_n
Если i = j R_i,j,k = ε|x₁|x₂|..|x_n

При k > 0

R_i,j,k = R_i,j,k-1 | R_i,j,k-1 R_k,k,k-1* R[k][j][k — 1]

_k,j,k-1

Ответом будет:
R_{s, t₁, n} | R_{s, t₂, n} |… | R_{s, t_p, n}

Регулярного выражения -> ε-НКА .

Вот представление основных операций регулярных выражений в виде ε-НКА.

Дале разбираем это выражение рекурсивным спуском и строим ε-НКА.

Чтобы обработать Регулярное выражение построим для ε-НКА, а потом получим из ε-НКА ДКА, который очень легко обрабатывать.