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

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

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

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

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

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

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

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

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

Таблица 3.1.

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

П₁ ={ A ₁ ¹, A ₂ ¹}; A ₁ ¹={ a _{1, a 2, a 5}, 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.

Таблица 3.3.

Таблица 3.4.

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

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

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

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

Таблица 3.5.

a1* a2*=a1, a3*=a2 a4* a5*=a3 Рис. 3.14. Рис. 3.15.