Свойство доказано. Покажем, что все состояния автомата Á являются отличимыми.

Покажем, что все состояния автомата Á являются отличимыми.

Пусть qⁱ, q^jÎ Q^*. Тогда состояния q_x(i) и q_x(j) - отличимые. Поскольку = и = , то ¹ . Следовательно, состояния qⁱ иq^j также являются отличимыми.

Поскольку "i( = ) и "i( = ), то множества функций, вычисляемых автоматами Áи Â, совпадают.

Окончательно получаем, что автоматы Áи Â - эквивалентные, причем автомат Á - минимальный.