Минимизация автомата

Каждый остаточный оператор реализуется в некотором состоянии автомата. Отсюда следует, что у любого автомата , реализующего ограниченно-детерминированный оператор , число состояний не меньше числа различных остаточных операторов оператора :

. (13)

Автомат с наименьшим числом состояний, реализующий ограниченно-детерминированный оператор , называется минимальным автоматом оператора .

Построенный при доказательстве последней теоремы автомат – минимальный.

Теорема. Минимальный автомат единственен с точностью до обозначения состояний.

Из теоремы следует признак минимальности автомата: автомат будет минимальным, если для любых двух его состояний и реализуемые в этих состояниях остаточные операторы различны.

Задача минимизации автомата: для данного автомата построить минимальный автомат, реализующий ограниченно-детерминированный оператор . Рассмотрим алгоритм ее решения.

Пусть . В процессе работы алгоритма строятся разбиения множества на непересекающиеся классы:

.

На очередном шаге алгоритма происходит измельчение предыдущего разбиения до тех пор, пока это возможно. Классы разбиения после завершения алгоритма будут состояниями минимального автомата.

1-й шаг. Состояния и отнесем к одному классу, если

.

Получим разбиение :

.

-й шаг. Пусть на -ом шаге получено разбиение :

.

Состояния и отнесем к одному классу нового разбиения, если выполнены два условия:

1) и входят в один класс предыдущего разбиения ;

2) для каждого символа состояния и входят в один класс предыдущего разбиения .

Обозначим через класс, в который входит состояние . Тогда условия 1) и 2):

1) ;

2) .

Алгоритм заканчивает работу, когда на некотором шаге не произойдет дальнейшего измельчения разбиения: . Последнее разбиение :

.

Тот факт, что алгоритм закончил работу можно выразить следующим образом:

.

Строим автомат :

, , , , .

Автомат реализует тот же словарный оператор, что и автомат , и является минимальным.