ПТЦА Лекция_____ Лист___
Минимизация числа внутренних состояний полностью определенных автоматов
Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.
Основная идея этого метода заключается в разбиении всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Т.о. получающийся в результате минимальный автомат имеет столько состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Для пользования методом введем несколько определений.
Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.
Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.
1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.
Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.
По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.
Если для некоторого i разбиения состояний автомата на (i+1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на - классы эквивалентности.
Разбиение множества внутренних состояний автомата на - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.
Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.
Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.
Из таблицы выходов получаем разбиение на 1-классы эквивалентности 1, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами:
1 = {B1, B2}; B2 = {a1, a2, a5, a6}; B2 = {a3, a4}
Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности Ci и разбиение 2 = {C1, C2, C3}, где С1 = {a1, a1}, C2 = {a5, a6}, C3 = {a3, a4}. Сравнивая 2 и 1, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 18), опять заменяя в таблице переходов состояния ai соответствующими классами эквивалентности Ci.
D1 = {a1, a2}, D2 = {a5, a6}, D3 = {a3, a4}.
Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.