Не полностью описанные автоматы.

До сих пор мы рассматривали полностью описанные автоматы. Практически функции и обычно бывают лишь частично определены. Системы обычно проектируются по частям и некоторые входные строки либо вообще не встречаются, либо встречаются в ситуациях, в которых выход нас не интересует. Поэтому некоторые позиции в таблицах состояний (или ребра в диаграммах состояний) отсутствуют. Такие позиции называются безразличными, в таблицах их обозначают прочерком.

Сначала казалось, что следует как-нибудь заполнить безразличные позиции в таблице и затем минимизировать получившийся полностью описанный автомат. Предполагалось, что выбор наименьшего из получившихся минимальных автоматов добавит искомый автомат.

Однако для многих не полностью описанных автоматов процедура такого вида не приводит к минимизации.

Пусть задан не полностью описанный автомат.

Если для этого автомата считать, что выход в состоянии считавшего 0, был иногда 0, а иногда 1, то автомат можно свести к двум состояниям. Если же настаивать, чтобы выход был всегда одним и тем же, то редукция невозможна.