Кодировка входных и выходных сигналов автомата обычно определена конкретной задачей. Единственная функция состояний заключается в том, чтобы определять зависимости между входами и выходами. Любое множество состояний, выполняющих эту функцию, является допустимым вне зависимости от того, имеют эти состояния интуитивно понятную интерпретацию или нет. Кодировка состояний полностью определятся разработчиком модели. Различное кодирование может влиять на надежность устройства, скорость его переключения и т.д.
Проблема оптимального кодирования состояний при различных критериях оптимальности до сих пор остается актуальной. Существуют некоторые традиционные подходы, позволяющие заменять одно множество состояний другим – оптимальным или минимальным в том или ином смысле. Такая замена осуществляется на основе понятия «эквивалентности».
Пусть A =
