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

Свойства как в предыдущем задании.

Если два состояния являются k-эквивалентными, то они являются и l-эквивалентными для каждого l<=k. Если два состояния являются k-различимыми, то они являются и l-различимыми для каждого l>=k.

K-эквивалентным разбиением автомата (Pk) называется разбиение его на классы k-эквивалентности (åk1, åk2, åk3,…), такие что все состояния, принадлежащие одному классу должны быть k- эквивалентными. все состояния, принадлежащие разным классам должны быть k-различимыми.

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

Свойства k-эквивалентного разбиения

• Ни одно состояние не может принадлежать одновременно двум k-эквивалентным классам, поскольку это обозначало бы, что это состояние является k-различимым по отношению к самому себе. Следовательно, общее  число состояний в Pk равно общему числу состояний в автомате.
• k-эквивалентное разбиение автомата единственно.
• Состояния, разобщенные в Pk являются разобщенными и в Pk+1.
• Если автомат имеет два различимых, но k-эквивалентных состояния, то он также имеет два состояния, которые являются k-эквивалентными, но k+1 различимыми.

Теорема. Pk+1 является собственным разделением Pk, если не во всех класса Pk смежные состояния являются эквивалентными. В противном случае Pk и Pk+1 совпадают.

Если Pk = Pk+1, то Pk = Pi  для любого i>k.