§ 9.7. Минимизация последовательностной машины в случае, когда она работает как конечный автомат

Предположим, что задана основная таблица конечного автомата с алфавитом состояний . Произведем перекодировку символов, заменив на , и положим , где — число символов . Тогда в заданной основной таблице конечного автомата все символы заменяются на символы с сохранением индекса.

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

Множество допустимых входных последовательностей может быть ограничено или неограничено.

Рассмотрим два случая — случай, когда на входные последовательности не наложено никаких ограничений, и случай, когда входные последовательности Ограничены условием — не могут появляться последовательности, имеющие два одинаковых символа подряд.