3.11. Минимальная форма

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

то

    (3.15)

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

Процесс отыскания минимальной формы автомата называется минимизацией автомата. Минимизация автомата состоит в определении эквивалентного разбиения Жив последующем применении (3.15) для построения Так как при применении (3.15) все состояния принадлежащие одному и тому же классу эквивалентности, дают один и тот же результат, то индивидуальное распознавание каждого состояния становится ненужным; для целей минимизации важно распознавание класса, к которому принадлежит каждое состояние. Поэтому всем состояниям принадлежащим классу эквивалентности можно приписать общее обозначение, например, . После этого (3.15) может быть интерпретировано как формулировка того, что автомат получается из автомата путем «объединения» одинаково обозначенных состояний в одно состояние. Способы, которыми это объединение производится, существенно зависят от того, каким образом определен автомат — таблицей, графом или матрицей. Эти способы будут описаны ниже. Хотя понимание этих способов облегчается благодаря предшествующей интуитивной интерпретации условия (3.15), их справедливость не зависит от этой интерпретации и вытекает непосредственно из самого условия.

Таблица переходов . Если заданы таблица переходов и эквивалентное разбиение автомата М, то таблица переходов автомата может быть построена следующим образом: (1) заменим обозначение каждого состояния, которое имеется в таблице переходов на обозначение класса, которому данное состояние принадлежит; (2) из каждой группы строк с одинаковыми обозначениями в клетках основного столбца (все такие строки являются одинаковыми в обеих подтаблицах вычеркнем все строки, кроме одной. Полученная при этом таблица является таблицей переходов

Например, автомат представленный таблицей 3.2, имеет классы эквивалентности Обозначим их произвольно 1, 2, 3, 4 и 5 соответственно. Делая первый шаг процедуры, заменим каждое обозначение «1», «3», и «8» в основном столбце и в подтаблице таблицы 3.2 на «1», каждое «2» и «4» - на «2»,

«5» и «7» — на «3», «6» — на «4», «9» — на «5». Полученная в результате таблица переходов приведена в таблице 3.14. Вычеркивание всех повторяющихся строк дает таблицу переходов АТ, показанную в таблице 3.15.

Таблица 3.14. Шаг 1 при построении таблицы переходов для автомата

Таблица 3.15. Автомат

Граф переходов М. Если заданы граф переходов и эквивалентное разбиение автомата М, то граф переходов автомата М может быть построен следующим образом: (1) заменим обозначение каждого состояния, которое имеется в графе переходов М, на обозначение класса, к которому относится данное состояние; (2) объединим все одинаково обозначенные состояния (рассматривая дуги графа как «гибкие связи») и представим объединенные состояния одним состоянием, имеющим общее обозначение; (3) из

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

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

Рис. 3.9. Автомат

Матрица переходов М. Если заданы матрица переходов и классы эквивалентности автомата М, то матрица переходов автомата М может быть построена следующим образом: (1) произведем симметрическую перестановку и симметрическое разбиение [М], так чтобы строки (и столбцы) группировались соответственно классам эквивалентности М (в результате получим матрицу такую же, как окончательная матрица получаемая при матричном методе эквивалентного разбиения); (2) заменим все обозначения строк (и столбцов) каждой группы, представляющей класс эквивалентности, одним обозначением этого класса; (3) заменим каждую подматрицу в разбитой матрице одной клеткой, содержащей все пары вход - выход, которые имеются в любой строке этой подматрицы (все строки в любой такой подматрице содержат одно и то же множество пар вход - выход). Полученная в результате матрица будет матрицей переходов М.

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

построении таблицы переходов