Теория множеств. Тождества алгебры множеств. Основные понятия теории графов. Методы задания конечных автоматов. Синтез функциональной схемы конечного автомата, страница 35

, , , .

Получено разбиение , , , , .

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

, , , , , .

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

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

Если функция переходов  и функция выходов   определены не для всех пар , то автомат называют не полностью определенным, или частичным автоматом. В таблице переходов и выходов частичного автомата неопределенные значения помечают символом  « - ». В частичном автомате допустимы только те входные слова , для которых:

1) последовательность состояний, определенная функцией переходов не содержит неопределенного состояния;

2) определен заключительный выход. Последнее означает, что выходное слово автомата может содержать произвольное количество неопределенных символов, за исключением последнего символа.

Примеры:

Пусть частичный автомат находится, например, в состоянии  . Для заданного входного слова  построим последовательность состояний  и последовательность выходных сигналов:

Входное слово…………………………

Последовательность состояний……… 

Выходное слово………………………..

Видно, что слово  допустимо. Приведем два примера не допустимых слов:

Входное слово…………………………

Последовательность состояний……… 

Выходное слово………………………..

Для слова  не определена последовательность состояний.

Входное слово…………………………

Последовательность состояний……… 

Выходное слово………………………..

Для слова  не определен заключительный выход.

Говорят, что состояние  автомата  покрывает состояние  автомата , если любое входное слово, допустимое для   в состоянии , допустимо и для  в состоянии   и вызывает в обоих случаях одинаковые реакции всюду, где состояния автомата  определены.

Автомат  покрывает автомат , если для каждого состояния   автомата  есть хотя бы одно состояние автомата  покрывающее .

Задачу минимизации числа состояний автомата  можно рассматривать как задачу поиска автомата  покрывающего  с минимальным числом состояний.

Два состояния  и  называют совместимыми (), если