yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.4 Недетерминированный конечный автомат

Дискретная математика

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

 

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

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

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

 

30