Множество Si называется совместимым множеством, если все состояния в нем попарно совместимы. Совместимое множество Si называется максимальным совместимым множеством, если оно не содержится ни в каком другом совместимом множестве в качестве подмножества. К совместимым множествам относятся также все одноэлементные подмножества множества состояний.

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

Поиск всех максимальных совместимых множеств состояний любого автомата сводится к поиску всех максимальных независимых множеств в графе несовместимости, построенном для заданного автомата. Для решения этой задачи можно использовать метод, описанный в гл. 4, в результате применения которого получим множества {1, 2, 3, 4}, {2, 3, 4, 5} и {3, 4, 5, 6}.

Достижимая верхняя граница т числа всех максимальных совместимых множеств для автомата с числом состояний  так же, как и наибольшее число всех максимальных независимых множеств в графе, приведенное в гл. 4, выражается следующими формулами: где k – некоторое целое положительное число:
т = 2 • 3k – 1, если  = 3k – 1;
т = 3 • 3k – 1, если  = 3k;
т = 4 • 3k – 1, если  = 3k + 1.