ОПРЕДЕЛЕНИЕ. Состояния qi и qj автомата Á называются k-неотличимыми, если qi и qj неотличимы на входных словах

Состояния q_i и q_j автомата Á называются k-неотличимыми, если q_i и q_j неотличимы на входных словах, длина которых не превосходит k.

То есть q_i и q_j k-неотличимы, если

" ((½ ½ £ k ) ® ( ( ) = ( ))).

Обозначим как r_k - отношениеk-неотличимости состояний заданного автомата, т.е. q_i r_k q_j тогда и только тогда, когда q_i и q_j являются k-неотличимыми.

Отношение неотличимости состояний Á будем обозначать как e.

Последующие рассуждения проводятся в предположении, что задан произвольный, но фиксированный автомат, для которого определены отношения e и r_k, k = 1, 2, . . .

Упражнение. Показать, что отношение e и отношения r_k, k = 1, 2, . . . , являются отношениями эквивалентности на множестве состояний автомата Á.