Состояния qi и qj автомата М несовместимы, если существует такая входная последовательность, допустимая для qi и qj, что заключительные выходные символы, вызываемые этой последовательностью при начальных состояниях qi и qj, не совпадают. Состояния qi и qj автомата М совместимы, если они не являются несовместимыми.

Отношение совместимости на множестве состояний автомата рефлексивно, симметрично, но не транзитивно. Из этих свойств отношение несовместимости обладает только симметричностью.

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

В некоторых случаях совместимость или несовместимость состояний устанавливается непосредственно. Пусть qi и qj – состояния некоторого автомата М. Если существует столбец таблицы выходов, в котором элементы строк qi и qj определены и различны, то состояния qi и qj несовместимы. Это явно несовместимые состояния.

Если строки qi и qj таблицы переходов совпадают везде, где их элементы определены, и строки qi и qj таблицы выходов также совпадают везде, где их элементы определены, то состояния qi и qj совместимы. Это явно совместимые состояния.

Совместимость состояний qi и qj, которые не являются ни явно совместимыми, ни явно несовместимыми, определяется с помощью цепи, порождаемой парой состояний qi, qj, которая находится так же, как цепь для полного автомата.