Состояние si автомата А и состояние sj автомата B эквиваленты (si = sj), если автоматы А и B, находясь в состояниях si и sj  соответственно, под воздействием любой входной последовательности выдает одинаковые выходные последовательности. Если состояния не эквиваленты, то их называют различимыми. Обозначения A и B могут относиться к одному и тому же автомату.

Свойства эквивалентности состояний: рефлективности (si=sj), свойством симметричности (если si=sj, то sj=si) и свойством транзитивности (если si=sj и sj=sk, то si=sk). Следовательно, эквивалентность состояний может рассматриваться как обычное отношение эквивалентности, которое применимо к множествам любой мощности. Различимость состояний не обладает свойствами рефлективности и транзитивности, следовательно, может относиться только к парам состояний.

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

Если строки si и sj в таблице выходов автомата различаются, то si¹sj 

Если строки si и sj в таблице переходов-выходов автомата совпадают, то si=sj.

Если строки si и sj в таблице переходов-выходов автомата становятся одинаковыми при замене каждого обозначения si на sj (или наоборот), то  si=sj.