Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов. Такие состояния исключаются из таблицы переходов. Процедура поиска недостижимых состояний следующая:
Шаг 1: записать одноэлементное множество, в которое входит начальное состояние;
Шаг 2: дополнить это множество состояниями, в которые переходит автомат из состояний, уже присутствующих в множестве при воздействии любых входных символов;
Шаг 3: если на шаге 2 множество не пополняется новыми элементами, то получен исчерпывющий список достижимых состояний; остальные состояния КА недостижимы.
Конечный автомат, из которого исключены недостижимые и эквивалентные состояния называется минимальным КА.