Алгоритм преобразования НКА в эквивалентный ДКА

Приветствую, коллеги! Предлагаю Вам окунуться в мир теории формальных языков, в частности, в парадигму конечных автоматов.

Цель данной статьи: познакомить Вас с алгоритмом построения детерминированного конечного автомата из недетерминированного конечного автомата. И сразу куча вопросов: зачем понадобилось данное преобразование, что такое конечный автомат, что такое ДКА и НКА и зачем мне это знать? Начнём с мотивации.

Зачем?

Любой алгоритм можно представить в виде конечного автомата. Обоснованность данного высказывания стоит искать в теории вычислений, связанной с небезызвестной машиной Тьюринга. Теория — это классно, теория — это супер… давайте практику.

Регулярные выражения строятся на КА.
Синтаксические анализаторы работают на КА – привет, компиляторы!
Известный алгоритм поиска множества паттернов в тексте Ахо-Корасик использует идею конечного автомата.

Надеюсь, этого достаточно, чтобы убедить вас в важности понимать данную конструкцию 😊

Пачка определений

Конечный автомат (КА) – пятёрка объектов, вместе образующих единую систему. Более формально: КА = {Q, ∑, δ, , F}, где Q – конечное мн-во состояний, ∑ - входной алфавит, δ – правила перехода, ∈ Q - начальное состояние, F ∈ Q - конечное мн-во заключительных состояний.

Давайте на примере. Дан конечный автомат:

Q – это все большие кружочки, обозначающие состояния КА. В данном примере Q = { , ,,,}. Символы, обозначающие такие состояния называют нетерминальными.

∑ — это все символы, по которым можно совершить переход к другим состояниям, т. е. все символы над стрелочками. В данном примере ∑ = {a}. Символы, входящие в это множество, называют терминальными. Про ε обязательно поговорим ниже – терминальным символом это не является и в алфавит автомата не входит.

= { } - это состояние, из которого начинается автомат.

F = { } - состояние, в котором КА заканчивается. На рисунках часто обозначают как двойной кружок, либо к нетерминальному символу приписывают нижний индекс f.

δ – А это некий свод правил, показывающий, как КА будет совершать переход. На рисунке эти правила представляют собой стрелочки. Записывается правило так: δ( , a) =
Т.е. пройдя из состояния по символу a попадём в состояние . Часто равенство не пишут, просто обозначая существование такого перехода.

Отлично, с этим разобрались! Ещё парочка определений.

Недетерминированный конечный автомат (НКА) – это КА, у которого есть 2 и более переходов по одному и тому же символу. Давайте на примере.

Это очень маленький НКА – из существуют как минимум два правила перехода с символом a. По какому же правилу нам пойти? Если встали на подобную развилку, то программист сам решает, куда направиться дальше. Но что, если нам нужна определённость? Для этого есть детерминированный КА.

Детерминированный конечный автомат (ДКА) – это КА, у которого гарантированно нет случая, описанного выше, а также отсутствуют ε-переходы. Более формально: не существует δ( , a) = и δ( , a) =

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

ε-переход – это переход по пустому символу. Нам на вход подаётся строка, которую мы считываем по одному символу. Считали символ – выполнили по этому символу переход к следующему состоянию. Считываем следующий и так далее. А ε-переход сигнализирует о том, что для перехода к состоянию нам вообще не нужен символ – берёшь и переходишь. Согласитесь, что было бы классно их убрать? Посмотрите на картинку ниже:

А давайте возьмём и упростим наш автомат – схлопнем ребро с ε-переходом. Он же нам совсем не нужен, ещё и автомат сократим. А давайте:

Концептуально изменился наш автомат? Ну не. Допустим нам пришёл на вход символ a – в первом случае мы сначала перейдем по ε-переходу, а затем по символу а перейдём в . Во втором случае мы сразу же перейдём по символу а в .

Этот трюк нам пригодится в алгоритме. Теперь, зная, что означает ε, нужно ввести 3 операции:

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

Алгоритм Томпсона

Как сделать из НКА ДКА? Убрать одноимённые переходы и избавиться от ε-переходов. В алгоритме Томпсона если рассматривать КА как граф, то это классический BFS (обход в ширину), с схлопыванием ε-переходов и объединением состояний, в которые ведут одноимённые переходы. Давайте к алгоритму, а затем и к примеру – там будет понятнее.

Шаг 1. Помещаем в очередь Queue множество, состоящее только из стартовой вершины.
Шаг 2. Затем, пока очередь не пуста выполняем следующие действия:

• Достаем из очереди множество, назовем его q

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

• Если в множестве q хотя бы одна из вершин была терминальной в НКА, то соответствующая данному множеству вершина в ДКА также будет терминальной.

Отлично! Из-за разности реализации конечных автоматов и разных языков программирования я приведу в качестве алгоритма псевдокод. В конце статьи Вы можете найти ссылку на репозиторий, где реализован данный алгоритм на C#.

Вход: НKA = (Q, Σ, δ, q0, F).
Выход: ДКА = (Q', Σ, δ', q0', F').

Q′= ∅
δ′ = ∅
Queue = ∅
currStates = ∅ // Мн-во состояний из очереди
newStates = ∅ // Мн-во состояний, в которые можно попасть из currStates
Queue = Queue ∪ q0
while (Queue ∉ ∅)
	currStates = Queue.pop()
    currStates = currStates ∪ ε-closure(currStates)
    foreach (a ∈ Σ)
    		newStates = move (currStates, a)
        	if (ε-closure(newStates) ∉ Q′)
        		Queue = Queue ∪ newStates
            		Q′ = Q′ ∪ ε-closure(newStates)
        	end
        	if (newStates ∉ ∅)
        		δ′ = δ′ ∪ δ(currStates, a)
        	end
    end foreach
end while

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

Формальное доказательство эквивалентности автоматов опустим – кому интересно, вот тут можно почитать его, а тут – посмотреть. Но я забыл рассказать про одну важную вещь! Как находить множество ε-closure(Q)?

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

Алгоритм нахождения ε-closure(Q).

Вход: Q
Выход: ReachableStates

ReachableStates = ∅
nextStates = ∅
foreach (q ∈ Q)
	nextStates = ε-closure(q)
  	if (nextStates ∉ ∅)
    		if (nextStates ∉ ReachableStates)
      			ReachableStates = ReachableStates ∪ nextStates
        	end
    end
end foreach

Предлагаю вам самим попробовать пройтись по этому алгоритму и найти ε-closure(Q) для данного КА с Q = {1, 2, 3, 4, 5, 6, 7, 8, 9}:

Теперь, зная всё это, мы можем подойти к примеру преобразования.
Пример. Задан недетерминированный конечный автомат ∑ = {0, 1, 2, ,}:

Нужно получить эквивалентный ДКА.

Приведём все шаги алгоритма для данного примера:
delta δ’ – показывает, какое правило перехода мы добавили
Изначально в очередь кладём начальное состояние.
Номер итерации: 0
Q’: ∅
Queue: S
Cur: S
delta δ’: δ(S, 0)

Номер итерации: 1
Q’: S
Queue: B
Cur: B
delta δ’: δ(B, +), δ(B, 0)

На этой итерации мы схлопываем ε-переход, получая состояние DE, вместо D и E.
Номер итерации: 2
Q’: S, B
Queue: D
Cur: DE
delta δ’: δ(DE, 0)

Номер итерации: 3
Q’: S, B, DE
Queue: F
Cur: F
delta δ’: δ(F, ,)

Номер итерации: 4
Q’: S, B, DE, F
Queue: G
Cur: G
delta δ’: δ(G, 1)

Номер итерации: 5
Q’: S, B, DE, F, G
Queue: H
Cur: H
delta δ’: δ(H, ,)

Номер итерации: 6
Q’: S, B, DE, F, G, H
Queue: J
Cur: J
delta δ’: δ(J, 2) – переход в состояние qfE

На этой итерации мы схлопываем два состояния (qf и E) в одно (qfE), так как в оба состояния ведёт один и тот же терминал – 2.
Номер итерации: 7
Q’: S, B, DE, F, G, H, J, qfE
Queue: qfE
Cur: F
delta δ’: δ(qfE, 0) – переход в состояние F

F не добавляем, так как оно уже есть в мно-ве
Номер итерации: 8
Q’: S, B, DE, F, G, H, J, qfE
Queue: ∅
Cur: ∅
delta δ’: -

Очередь пуста. Алгоритм завершён.
Итого, получаем:
Q’: S, B, DE, F, G, H, J, qfE
δ’:
δ(S, 0)
δ(B, 0)
δ(B, +)
δ(DE, 0)
δ(F, ,)
δ(G, 1)
δ(H, ,)
δ(J, 2)
δ(qfE, 0)
F’: qfE
Граф переходов ДКА имеет вид:

Конец. Как и обещал, ссылка на репозиторий, где реализован данный алгоритм.

Спасибо за прочтение! Это была моя первая статья на Хабре: буду рад любой критике или похвале. Удачного дня!