Построение детерминированного конечного автомата по недетерминированному

Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.

Алгоритм 3.2. Построение детерминированного конечного автомата по недетерминированному.

Вход. НКА M = (Q, T, D, q0, F).

Выход. ДКА M' = (Q', T, D', q0', F'), такой что L(M) = L(M').

Метод. Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.

В алгоритме будут использоваться следующие функции:

e-closure(R) (R

Q) - множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, т.е. множество

move(R, a) (R

Q) - множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество

Вначале Q' и D' пусты. Выполнить шаги 1-4:

Определить q0' = e-closure({q0}).

Добавить q0' в Q' как непомеченное состояние.

Выполнить следующую процедуру:

while (в Q' есть непомеченное состояние R){

пометить R;

for (каждого входного символа a
T){

S = e-closure(move(R, a));

if (S
){

if (S
Q')

добавить S в Q' как непомеченное состояние;

определить D'(R, a) = S;

}

}

}

Определить F' = {S|S
Q', S
F
}.

Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.10.

Рис. 3.10:

Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык[10].

Пусть дано регулярное выражение r в алфавите T. К регулярному выражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

Алгоритм будет

оперировать с синтаксическим деревом для пополненного регулярного выражения (r)# , каждый лист которого помечен символом a

{e, #}, а каждая внутренняя вершина помечена знаком одной из операций: .

(конкатенация), | (объединение), * (итерация).

Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ

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

Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, firstpos, lastpos и followpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция followpos вычисляется через три остальные функции.

Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют

первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово, определим nullable(n) = true, а для остальных узлов nullable(n) = false.

Таблица для вычисления функций nullable, firstpos и lastpos приведена на рис. 3.11.

Рис. 3.11:

Пример 3.7.

Рассмотрим теперь алгоритм построения ДКА с минимальным числом состояний, эквивалентного данному ДКА [10].

Пусть M = (Q, T, D, q0, F) - ДКА. Будем называть M всюду определенным, если D(q, a)

для всех q

Q и a

Лемма. Пусть M = (Q, T, D, q0, F) - ДКА, не являющийся всюду определенным. Существует всюду определенный ДКА M', такой что L(M) = L(M'). Доказательство. Рассмотрим автомат M' = (Q

{q'}, T, D', q0, F), где q'

Q - некоторое новое

состояние, а функция D' определяется следующим образом:

Для всех q

Q и a
T, таких что D(q, a)
, определить D'(q, a) = D(q, a).

Для всех q

Q и a
T, таких что D(q, a) =
, определить D'(q, a) = q'.

Для всех a

T определить D'(q', a) = q'.

Легко показать, что автомат M' допускает тот же язык, что и M. __

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

Алгоритм 3.4. Построение ДКА с минимальным числом состояний.

Вход. Всюду определенный ДКА M = (Q, T, D, q0, F).

Выход. ДКА M' = (Q', T, D', q0', F'), такой что L(M) = L(M') и M' содержит наименьшее возможное число состояний.

Метод. Выполнить шаги 1-5:

Построить начальное разбиение

множества состояний из двух групп: заключительные состояния Q и остальные Q - F, т.е.

= {F, Q - F}.

Применить к

следующую процедуру и получить новое разбиение

new:

for (каждой группы G в

){

разбить G на подгруппы

так, чтобы

состояния s и t из G оказались

в одной подгруппе тогда и только тогда,

когда для каждого входного символа a

состояния s и t имеют переходы по a

в состояния из одной и той же группы в

;

заменить G в

new на множество всех

полученных подгрупп;

}

Если

new =

, полагаем

res =

и переходим к шагу 4, иначе повторяем шаг 2 с

new.

Пусть

res = {G1, ..., Gn}. Определим:

Q' = {G1, ..., Gn};

q0' = G, где группа G

Q' такова, что q0

F' = {G|G

Q' и G

};

D'(p', a) = q', если D(p, a) = q, где p

p' и q

q'.

Таким образом, каждая группа в

res становится состоянием нового автомата M'.

Синтаксическое дерево для пополненного регулярного выражения (a|b)*abb# с результатом вычисления функций firstpos и lastpos приведено на рис. 3.12. Слева от каждого узла расположено значение firstpos, справа от узла - значение lastpos. Заметим, что эти функции могут быть вычислены за один обход дерева.

Рис. 3.12:

Рис. 3.13:

Если i - позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка ...cd..., входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j - вхождению

d.

Функция followpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам.

1. Пусть n - внутренний узел с операцией .

(конкатенация), u и v - его потомки. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений followpos(i) множество firstpos(v).

2. Пусть n - внутренний узел с операцией *

(итерация), u - его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений followpos(i) множество firstpos(u).

Пример 3.8. Результат вычисления

функции followpos для регулярного выражения из предыдущего примера приведен на рис. 3.13.

Алгоритм 3.3. Прямое построение ДКА по регулярному выражению.

Вход. Регулярное выражение r в алфавите T.

Выход. ДКА M = (Q, T, D, q0, F), такой что L(M) = L(r).

Метод. Состояния ДКА соответствуют множествам позиций.

Вначале Q и D пусты. Выполнить шаги 1-6:

Построить синтаксическое дерево для пополненного регулярного выражения (r)#.

Обходя синтаксическое дерево, вычислить значения функций nullable, firstpos, lastpos и followpos.
Определить q0 = firstpos(root), где root - корень синтаксического дерева.

Добавить q0 в Q как непомеченное состояние.

Выполнить следующую процедуру:

while (в Q есть непомеченное состояние R){

пометить R;

for (каждого входного символа a
T , такого, что

в R имеется позиция, которой соответствует a){

пусть символ a в R соответствует позициям

p1, ..., pn, и пусть S =

1<i<nfollowpos(pi);

if (S
){

if (S
Q)

добавить S в Q как непомеченное состояние;

определить D(R, a) = S;

}

}

}

Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #.

Пример 3.9. Результат применения алгоритма 3.3 для регулярного выражения (a|b)*abb приведен на рис. 3.14.

Рис. 3.14:

Если группа содержит начальное состояние автомата M, эта группа становится начальным состоянием автомата M'. Если группа содержит заключительное состояние M, она становится заключительным состоянием M'. Отметим, что каждая группа

res либо состоит только из состояний из F, либо не имеет состояний из F. Переходы определяются очевидным образом.

Если M' имеет «мертвое» состояние, т.е. состояние, которое не является допускающим и из которого нет путей в допускающие, удалить его

и связанные с ним переходы из M'. Удалить из M' также все состояния, недостижимые из начального.

Пример 3.10. Результат применения алгоритма 3.4 приведен на рис. 3.15.

Рис. 3.15:

Содержание раздела