§4. Процедура минимизации конечных автоматов.

Актуальность проблемы минимизации конечных автоматов уже была приведена выше. В реальном устройстве (калькулятор, компьютер) увеличение числа внутренних состояний ведёт к увеличению числа микросхем, что в свою очередь может привести к росту стоимости, к более частым поломкам. Значит, уменьшение числа внутренних состояний автомата без ограничения его возможностей ведёт к экономии и надёжности в работе.

Процедура минимизации основана на рассмотрении отношений эквивалентности между упорядоченными парами. Рассмотрим автомат, заданный таблицей внутренних состояний:

	Следующее сост.	Выход

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

,.

В записи классов эквивалентности для краткости мы пишем 1 вместо S₁ и т.д. При составлении этого предварительного разбиения мы ориентируемся на выходную последовательность. Это разбиение определяет график соответствующего отношения эквивалентности. Т.к. отношение рефлексивно и симметрично, то его график легко восстанавливается по множеству тех пар, для которыхпри всех значений входного символа.

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

,

Т.к. и- это классы эквивалентности относительно, то имеем следующие соотношения:,,,и т.д.

Множество состоит из элементов множестваи еще пар,и. Например, входной символпереводит парув пару, а эта последняя пара принадлежит. Добавление этихпар к определяет новое разбиение на классы эквивалентности:

: ,,.

Определим теперь множество . Оно состоит из элементов множества и еще пар и. Например, входной символпереводит парув пару, а эта последняя пара принадлежит множеству .

При разбиении имеем следующие классы эквивалентности:

, ,,.

Множество состоит из элементов множестваи из пар,,,,,. Поэтому разбиениесостоит из следующих классов эквивалентности:

, ,,,.

Дальнейший перебор показывает, что и.

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

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

На следующем примере показан результат этой процедуры, примененной к автомату, рассмотренному раньше.

	Следующее сост.	Выход

Этот автомат уже является минимальным. Это значит, что он не содержит эквивалентных состояний.

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

Пример. Рассмотрим конечный автомат с пятью состояниями, заданный таблицей.

	Следующее сост.	Выход

Имеем , , , . Это приводит к разбиению : ,. Тогда функция перехода при считывании единицы имеет вид, кроме того. Однако ,поэтому (т.к. и ).

Следующее разбиение состоит из классов эквивалентности:

,,.

Дальнейшего измельчения не происходит, т. к. функция переводит каждый элемент класса эквивалентности в тот же класс. Итак, состоянияиможно склеить в одно состояние, а состоянияи- в состояние. Состояниеобозначаемтеперь . Новый минимальный автомат, покрывающий предыдущий, можно изобразить в виде:

	Следующее сост.	Выход