Алгоритм минимизации конечного автомата
4.4. Алгоритм минимизации конечного автомата
Шаг 1: два состояния s и t относим в один класс , если для любого входного символа x значение функции выхода s совпадает со значениями функции выхода t. В результате получим r классов:
.
M
Шаг k: два состояния s и t из одного класса , полученного на предыдущем шаге, относим в один класс , если для любого значения входного символа значения функций состояний принадлежат одному и тому же классу из предыдущего шага. Если шаг k не изменяет разбиения, то процесс останавливается. Доопределяем функции перехода и выхода и строим таблицу переходов –выходов.
Пример. Минимизировать автомат, заданный таблицей:

Шаг 1: Первое, третье и четвертое состояния отнесем в один класс состояний, а второе, пятое и шестое – в другой:
; 
Шаг 2: Выпишем значения функции переходов для состояний из класса :
; ; 
; ; 
; ; 
Видно, что 1 и 3-е состояния относим в один класс этого шага , а четвертое состояние – в другой . Проанализировав аналогичным образом значения функции выходов для состояний из класса , видим:
; ; 
; ; 
; ; , т.е. все они остаются в одном классе. В результате получим разбиение на классы:
; ; 
Шаг 3: ; ; . Дальнейшего разбиения классов не происходит, поэтому процесс останавливается. Класс назовем состоянием , класс состояний назовем состоянием , а класс – состоянием .
Построим таблицу переходов–выходов:

Построенный автомат – минимальный.
|