Цепью, порождаемой парой состояний qi, qj частичного автомата М, назовем множество С, элементами которого являются следующие пары состояний: сама пара qi, qj; все пары вида (a, qk), (a, ql), где (a, qk) и (a, ql) определены и различны, если qk, ql  C. Другие пары не входят в С.

Справедливо следующее утверждение, которое доказывается точно так же, как утверждение 19.1.

У т в е р ж д е н и е 20.1. Состояния qi и qj автомата М являются совместимыми, если и только если в цепи, порождаемой парой состояний qi, qj, нет ни одной пары явно несовместимых состояний. В этом случае все пары, принадлежащие данной цепи, являются парами совместимых состояний.

Совместимость удобно представлять булевой матрицей совместимости, строкам и столбцам которой соответствуют состояния автомата и элемент на пересечении i-й строки и j-го столбца имеет значение 1, если и только если состояния qi и qj совместимы. Процесс установления совместимости состояний частичного автомата не отличается от процесса установления эквивалентности состояний полного автомата, описанного в разд. 19.2.

Пусть задан автомат, таблицу переходов и выходов которого представляет табл. 20.5.