Минимизация числа внутренних состояний полностью определенных автоматов

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

Определение 1. Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.

Определение 2. Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

Определение 3. 1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Определение 4. Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение до -эквивалентных состояний и -класс эквивалентности.

Определение 5. Если для некоторого разбиения состояний автомата на ( +1) - класс совпадает с разбиением на -класс, то оно является разбиением и на ¥-класс эквивалентности.

Определение 6. Разбиение множества внутренних состояний автомата на ¥-класс и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

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

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

Из таблицы выходов (табл. 3.13) получаем разбиение на 1-классы эквивалентности , объединяя в эквивалентные классы состояния с одинаковыми столбцами:

, , .

Для получения 2-эквивалентных состояний составим таблицу 1-разбиения (табл. 3.14), заменяя в таблице переходов состояния соответствующими классами эквивалентности или . Из полученной таблицы 1-разбиения получаем 2-класс эквивалентности, которые обозначим и соответствующее разбиение , где , , .

Таблица 3.13

Матрицы переходов и выходов автомата Мили

Сравнивая и , отмечаем, что эти разбиения отличаются друг от друга.

Таблица 3.14

Таблица 1-разбиения

 

Поэтому аналогично строим таблицу 2-разбиения (табл. 3.15), опять заменяя в таблице переходов состояния соответствующими классам эквивалентности .

Из полученной таблицы 3.15 2-разбиения получаем 3-класс эквивалентности , которому соответствует разбиение , где , , .

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

Таблица 3.15

Таблица 2-разбиения

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

Таблица 3.16

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

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

Дата добавления: 2015-07-08