Минимизация числа внутренних состояний абстрактных автоматов

Табличная форма представления матриц переходов и выходов.

На практике часто используется табличная форма представления матриц (рис. 3.12 и 3.13)

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

Эквивалентными называются такие два состояния автомата, замена которых одно на другое не изменяет результатов словарного преобразования на всем множестве допустимых входных слов. Можно говорить как о полной эквивалентности внутренних состояний (для входных слов неограниченной длины), так и о k-эквивалентности состояний (для слов длиной в k символов). В дальнейшем классы эквивалентных и k-эквивалентных внутренних состояний будут соответственно обозначаться как П и П_k.

Процедура минимизации числа внутренних состояний абстрактного автомата состоит из следующих шагов:

1. Находятся последовательные разбиения П₁ , П₂ ,…, П_k алфавита внутренних состояний на классы одно-, двух-, …, k-эквивалентных состояний, до тех пор, пока на каком-то k+1-м шагом не окажется, что П_k+1= П_k. Очевидно, что при достижении этого тождества можно утверждать, что П_k= П, т.е. что k-эквивалентные состояния являются полностью эквивалентными. Нетрудно увидеть, что число шагов этой процедуры не может превысить значения l -1, где l -размеры алфавита внутренних состояний автомата.

2. В каждом классе эквивалентности П выбирается по одному символу, которые и составляют новый алфавит внутренних состояний минимизированного автомата.

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

4. В качестве начального состояния автомата выбирается или начальное состояние исходного автомата, или любое ему эквивалентное.

Рассмотрим пример минимизации автомата Мили, заданного совмещенной таблицей переходов и выходов (табл. 3.1.).

Таблица 3.1.

Xi

a k

a 1

a 2

a 3

a 4

a 5

a 6

a 7

a 8

a 9

a 10

a 11

a 12

X1

a 10 Y1

a 12 Y1

a 3 Y2

a 7 Y2

a 3 Y1

a 7 Y2

a 3 Y1

a 10 Y1

a 7 Y2

a 1 Y2

a 5 Y2

a 2 Y2

X2

a 5 Y2

a 7 Y2

a 6 Y1

a 11 Y1

a 9 Y2

a 11 Y1

a 6 Y2

a 4 Y2

a 6 Y1

a 8 Y1

a 9 Y1

a 8 Y1

Класс П₁ выделяется из табл. 3.1. путем объединения тех внутренних состояний, которые характеризуются одинаковой реакцией на слова длиной в один символ. Заметим, что в понятие реакции входит только выходной сигнал, поскольку основным назначением автомата является осуществление словарного преобразования. Для класса П₁ выполняются:

П₁ ={ A ₁ ¹, A ₂ ¹}; A ₁ ¹={ a ₁, a ₂, a ₅, a₇, a₈}; A ₂ ¹={ a₃, a₄, a₆, a₉, a₁₀, a₁₁, a₁₂}.

Строим таблицу П₁ (табл. 3.2.), получая ее из совмещенной таблицы заменой символов исходного алфавита внутренних состояний на классы 1-эквивалентности.

Очевидно, что любая пара 1-эквивалентных состояний будет и 2-эквивалентна, если они любым входным сигналом будут переводиться в 1-эквивалентные. Практически это означает, что 2-эквивалентными будут те состояния, которые уже входя в тот или иной класс эквивалентности, в данной таблице имеют одинаковые столбцы. Тогда по табл. 3.2. для класса П₂ получаем: П₂ ={ A ₁ ², A ₂ ², A ₃ ², A ₄ ²}; A ₁ ²={ a₁, a₂};

A ₂ ²={ a₅, a₇, a₈}; A ₃ ²={ a₃, a₄, a_6, a₉, a₁₁}; A ₄ ²={ a₁₀, a₁₂}

Таблица 3.2.

Xi

ak, A^sp

A^11

A^12

a1

a2

a5

a7

a8

a3

a4

a6

a9

a10

a11

a2

X1

A^12

A^12

A^12

A^12

A^12

A^11

A^11

A^11

A^11

A^11

A^11

A^11

X2

A^11

A^11

A^12

A^12

A^12

A^12

A^12

A^12

A^12

A^11

A^12

A^11

Таблица 3.3.

Xi

ak, A^sp

A^21

A^22

A^23

A^24

a1

a2

a5

a7

a8

a3

a4

a6

a9

a11

a10

a12

X1

A^24

A^24

A^23

A^23

A^24

A^22

A^22

A^22

A^22

A^22

A^21

A^21

X2

A^22

A^22

A^23

A^23

A^23

A^23

A^23

A^23

A^23

A^23

A^22

A^22

Таблица 3.4.

Xi

ak, A^sp

A^31

A^32

A^33

A^34

A^35

a1

a2

a5

a7

a8

a3

a4

a6

a 9

a 11

a 10

a 12

X1

A^35

A^35

A^32

A^32

A^34

A^33

A^33

A^33

A^33

A^33

A^31

A^31

X2

A^32

A^32

A^34

A^34

A^34

A^34

A^34

A^34

A^34

A^34

A^33

A^33

Продолжая аналогичную процедуру и далее, соответственно получим класс эквивалентности П₃. Таблицы для всех этих классов: для П₂ - табл. 3.3., для П₃ - табл. 3.4.

Из табл. 3.5. видно, что П₃ = П, откуда можно составить совмещенную таблицу уже минимизированного автомата (табл. 3.5.).

Используя рассмотренную процедуру по отношению к автомату, представленному графом на рис. 3.14., легко показать, что тот автомат после минимизации полностью переходит в автомат Мили, граф которого помещен на рис. 3.15.

Аналогичную процедуру минимизации можно провести и для автомата Мура.

Таблица 3.5.

Xi	a k
a 1	a 5	a 8	a 3	a 10
X1	a 10 Y1	a 3 Y1	a 10 Y1	a 5 Y2	a 1 Y2
X2	a 5 Y2	a 3 Y2	a 3 Y2	a 3 Y1	a 8 Y1

Рис. 3.14. Рис. 3.15.

Дата добавления: 2014-01-05