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

 

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

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

а) входной алфавит 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}.