Построение минимального автомата

 

Для получения минимального автомата воспользуемся методом разбиения. Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества (блоки), такие, что неэквивалентные состояния попадают в разные блоки.

Условия эквивалентности состояний:

- условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими;

- условие преемственности: для всех входных символов состояния S и T должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны.

Сначала состояния разбиваются на 2 блока. Один содержит только допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:

) Если под действием какого-либо входного символа какая-то часть состояний данного блока переходит в состояния из другого блока, что нарушает условие преемственности, то необходимо разбить данный блок на части так, чтобы не нарушалось в одном блоке условие преемственности.

) Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение невозможно.

) За один раз можно разбить только один блок.

Обозначим {S1, S3} как {M}.

Поделим на группы допускающих, недопускающих состояний:

{{S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем {S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} повходуx4:

{{S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A, B, C}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} повходуx5:

{{S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err} повходуx5:

{{S, M, S2, S4, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10},

{D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, S2, S4, F, F1, F2, F5, F6, F9, Err} повходуx7: {{S, M, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, S2, S4, F, F1, F2, F5, F6, F9, Err} повходуx7:

{{S, M, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, F, F1, F2, F5, F6, F9, Err} повходуx4:

{{S, M, F, F1, F5, F9, Err}, {A, B, C}, {F2, F6}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, F, F1, F5, F9, Err} повходуx2:

{{S, M, F, F9, Err}, {A, B, C}, {F2, F6}, {F1, F5}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьемблок {S, M, F, F9, Err}, выделив начальное состояние и состояние ошибки:

{{S}, {M, F, F9}, {Err}, {A, B, C}, {F2, F6}, {F1, F5}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Дальнейшее разбиение невозможно. Полученные блоки состояний можно использовать для построения нового автомата, который эквивалентен исходному, и не содержит эквивалентных состояний. Для построения нового автомата, произведем замену обозначений блоков:

{S}                                              -> A

{M}                                   -> B

{F}                                     -> C

{F9}                         -> D

{F2, F6}                                     -> E

{F1, F5}                            -> F

{S2, S4}                                     -> G

{D, E}                                         -> H

{A, B, C}                                    -> I

{F3, F7, F10}                             -> J

{A1, B1, C1, D1, E1, F4, F8, F11} -> K

{Err}                        -> L

В соответствии с этими обозначениями мы получаем минимальный автомат, таблица переходов которого представлена таблицей 5.

 

Таблица 5. Таблица переходов минимального автомата

	x0	x1	x2	x3	x4	x5	x6	x7
A	L	С	L	I	L	B	L	L	0
B	G	L	L	L	L	G	L	L	0
C	L	L	L	D	L	F	F	L	0
D	J	L	L	L	L	L	L	L	0
E	L	L	L	L	J	L	L	L	0
F	L	L	E	L	L	L	L	L	0
G	L	L	L	L	I	L	L	L	0
H	L	A	L	L	L	K	L	L	0
I	L	L	L	L	K	L	L	H	0
J	L	L	L	L	L	L	K	L	0
K	L	L	L	L	L	L	L	L	1
L	L	L	L	L	L	L	L	L	0

 

Граф переходов минимального автомата построен на рис. 4. Для облегчения читаемости, на рисунке не изображено состояние Lи ведущие к нему переходы.

Рис. 4

Построение сети Петри

 

Построим для грамматики G' сеть Петри. Для этого, поставим в соответствие нетерминальным символам позиции (кружки) сети. А терминалам - переходы (планки) сети. Пометим позиции и переходы соответствующими нетерминалами и терминалами.

Позиции соединяются дугами только через переходы, а переходы - через позиции. Если в правой части некоторого правило вывода из R’ имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции, которые можно помечать символами левой части правил вывода с индексами 1, 2, ….

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

Выполнив эти действия, получаем сеть Петри (рис. 5).

 

Сеть Петри

Рис. 5

 

Для полноты соответствия построенной сети Петри распознающему автомату Мура, введем не показанную на рис. 5 заключительную позицию Z, в которую направим дуги из всех переходов, ранее не имевших исходящих дуг. В результате получим новую сеть Петри (рис. 6).

 

Сеть Петри с заключительной позицией Z

Рис. 6

 

Далее, необходимо минимизировать сеть Петри. Для этого определим в ней идентичные фрагменты. Итак, идентичными фрагментами являются позиции D и E c инцидентными им переходами x5 и x4. Также, позиции A, Bи С с инцидентными им переходами x4 и x7. Позиции S1 и S3, F2 и F5, F3 и F6, F1 и F4, F6 и F8можно склеить попарно. В результате получаем минимизированную недетерминированную сеть Петри (рис. 7).

 

Минимизированная сеть Петри

Рис. 7

Этот этап соответствует минимизации числа состояний автомата, но он выполнен для автомата, сохраняющего недетерминированность. Источником недетерминированности, очевидно, могут являться лишь позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами.

Недетерминированность устраняется склеиванием двух позиций P_l и P_k в одну (P_l, P_k). При этом позиции (P_l, P_k) инцидентны все исходящие дуги, являющиеся исходящими дугами позиций P_lиP_k.

В полученной сети Петри отсутствуют позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. А значит, сеть Петри (рис. 7) уже детерминированаи минимизирована.

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

 

S -> A S1, S3 -> B F ->C F7 ->D F2, F5 ->E F1, F4 ->F

S2, S4->G D, E->H A, B, C->I F3, F6, F8 ->J Z->K

 

Уберем переходы из сети Петри, дуги подпишем терминалами переходов, тогда получим граф переходов (рис. 8).

 

 

Граф переходов, полученный из сети Петри

Рис. 8

 

Сравнив полученный граф (рис. 8) с графом минимального автомата (рис. 4) мы видим, что они идентичны. Значит, минимальный автомат построен правильно.