Недетерминированный конечный автомат (в дальнейшем НКА) представляет собой обычный КА с той разницей, что в таблице переходов паре входной символ - состояние ставится в соответствие множество состояний(а не единственное, как в КА) и начальных состояний может быть несколько.
В процессе построения такого недетерминированного конечного автомата должны быть определены следующие параметры:
а) входной алфавит V (конечное множество входных символов и символ "конец цепочки");
б) конечное множество состояний S;
в) множество начальных состояний НКА - Sнач (состояний, с которых может начинать работу НКА при обработке новой цепочки);
г) множество допускающих состояний - Sдоп (подмножество множества состояний S, с которым сравнивается достигнутое НКА состояние после прихода символа "конец цепочки");
д) таблица переходов (управляющая таблица), которая паре текущее состояние - входной символ ставит в соответствие несколько новых состояний); если паре текущее состояние - входной символ нельзя поставить в соответствие ни одно состояние из множества S, то клетку таблицы переходов оставляют пустой.
Работу НКА можно интерпретировать двумя способами:
1. На некоторых шагах при распознании цепочки с помощью НКА есть множество выборов. Если имеется хотя бы одна последовательность состояний, при которой НКА заканчивает работу в допускающем состоянии, то такая цепочка будет допущена НКА.
2. При возникновении альтернативы при работе НКА в выборе начального состояния или перехода, автомат распадается на конечные автоматы по количеству альтернатив, которые работают параллельно. Если при поступлении символа "конец цепочки" хотя бы один из параллельно работающих КА находится в допускающем состоянии, то такая цепочка допускается.
Существует процедура эквивалентного преобразования НКА в КА по следующему алгоритму (преобразуется таблица переходов НКА):
1. Изобразить столбцы для входных символов и записать их.
2. В первой клетке первой строки записать как множество все на чальные состояния.
3. Заполнить остальные клетки этой строки(кроме последней): по таблице переходов НКА выписать в виде множеств все состояния, в которые переходят состояния, записанные в первой клетке через соответствующие входные символы.
4. В первой клетке очередной строки записать одно из новых множеств состояний, которые получены в п.3 при заполнении клеток таблицы переходов и выполнить п.3.
5. Закончить процесс построение таблицы переходов после того как будут исчерпаны все варианты множеств, которые появились в таблице.
6. При заполнении столбца с символом "конец цепочки" ставить "допустить", если в множество состояний первой клетки строки входит хотя бы одно допускающее состояние и "отвергнуть" в противном случае.
7. Переобозначить множества состояний как новые состояния и заново заполнить таблицу переходов(получена таблица переходов эквивалентного КА).
8. Определить остальные параметры КА по полученной таблице переходов.
Описанную выше процедуру проиллюстрируем на конкретном примере.
Задан НКА: -------T---T-----T-----¬
¦ S ¦ k ¦ n ¦ --+ ¦
V = { 0, 1, --+ }; Sнач = { A, B }; +------+---+-----+-----+
S = { A, B, C }; Sдоп = { B, C }. ¦-->A ¦ A ¦ B,C ¦ 0 ¦
¦-->B ¦ B ¦ C ¦ 1 ¦
Преобразовать заданный НКА в КА и ¦ C ¦ ¦ A,C ¦ 1 ¦
минимизировать полученный КА. L------+---+-----+------
Р Е Ш Е Н И Е
1.Выполним процедуру преобразования НКА в КА по описанному алгоритму: ------T-----T-----T------¬ ----T---T---T-----¬
¦ S ¦ k ¦ n ¦ ---+ ¦ ¦ S ¦ k ¦ n ¦ --+ ¦
+-----+-----+-----+------+ +---+---+---+-----+
¦ A,B ¦ A,B ¦ B,C ¦ 1 ¦ ¦ a ¦ a ¦ b ¦ 1 ¦
¦ B,C ¦ B ¦ A,C ¦ 1 ¦ ¦ b ¦ c ¦ d ¦ 1 ¦
¦ B ¦ B ¦ C ¦ 1 ¦ ¦ c ¦ c ¦ e ¦ 1 ¦
¦ A,C ¦ A ¦A,B,C¦ 1 ¦ ¦ d ¦ f ¦ g ¦ 1 ¦
¦ C ¦ ¦ A,C ¦ 1 ¦ ¦ e ¦ ¦ d ¦ 1 ¦
¦ A ¦ A ¦ B,C ¦ 0 ¦ ¦ f ¦ f ¦ b ¦ 0 ¦
¦A,B,C¦ A,B ¦A,B,C¦ 1 ¦ ¦ g ¦ a ¦ g ¦ 1 ¦
L-----+-----+-----+------- L---+---+---+------
Переобозначения состояний следующие:
a = { A, B }; b = { B, C }; c = { B }; d = { A, C }; e = { C };
f = { A }; g = { A, B, C }.
2.Проверим состояния полученного КА на достижимость:
{a} -->{a,b} --> {a,b,c,d} --> {a,b,c,d,e,f,g}
Все состояния КА достижимы.
3.Проверим состояния полученного КА на эквивалентность:
Первое разбиение множества состояний на подмножества по входному символу "конец цепочки": {f}; {a,b,c,d,e,g}.
Проанализируем воздействие входного символа "k" на второе
подмножество:
d --> f; e --> { } ; остальные остаются в этом подмножестве. Есть основания выделить d и e в отдельные подмножества.
Теперь разбиение будет иметь вид: {f}; {d}; {e}; {a,b,c,g}.
Проанализируем воздействие входного символа "n" на последнее подмножество:
b --> d; c --> e; a --> b; g --> g.
Состояния b и c переходят в другие группы и их нужно выделить; состояние а - в выделенное на этом шаге состояние b и на этом основании его тоже нужно выделить. В результате:{f}; {d}; {e}; {a}; {b}; {c}; {g}.
Вывод: эквивалентных состояний нет; полученный КА является минимальным.
4. По таблице переходов КА определим остальные его параметры:
V = { k, n, --+ }; Sнач ={a}; Sдоп = {a,b,c,d,e,g};
S = {a,b,c,d,e,f,g}.