Лемма 1. Состояния 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,..., являются отношениями эквивалентности на множестве состояний автомата Á.

Для всякого значения k справедливы включения:

r_k Ê r_{k+ 1} и r_k e.

Дата добавления: 2015-03-31