Доказательство. Предположим противное. Пусть qi и qj-неотличимые состояния, но для некоторого входного слова состояния j* (

Предположим противное. Пусть q_i и q_j-неотличимые состояния, но для некоторого входного слова состояния j* ( , q) и j* ( , q_j) являются отличимыми.

Пусть - такое входное слово, на котором различаются j*( , q_i) и j*( , q_j).

Тогда состояния q_i и q_j различаются на входном слове . Последнее заключение противоречит предположению о неотличимости состояний q_i и q_j.