Индуктивный переход. Пусть = a - произвольное слово длины m = k+ 1

Пусть = a - произвольное слово длины m = k+ 1. Тогда справедливы соотношения:

1) ( ) = ( ) Y(a, F^*( , qⁱ);

2) ( ) = ( ) y(a, j^*( ,q_x(i))).

По индуктивному предположению ( )= ( ).

Покажем, что y(a, F^*( , qⁱ) = y(a, j^*( ,q_x(i))).

Пусть j^*( , q_x(i)) = q_j. Тогда из вспомогательного индуктивного предположения следует, что состояния q_j и q_x(r), где q^r = F^*( , qⁱ) - неотличимые.

Поэтому справедливы равенства, доказывающие справедливость индуктивного перехода для основного свойства:

Y(a, F^*( , qⁱ) = Y(a, q^r) = y(a, q_x(r)) = y(a, q_j)= = y(a, j^*( ,q_x(i))).

Покажем справедливость индуктивного перехода для вспомогательного утверждения.

Рассмотрим состояния j^*( a, q_x(i)) и q_x(h), где q^h = F^* ( a, qⁱ). Покажем, что эти состояния неотличимые.

Так как q_j и q_x(r) Î Q_r, то состояния j^*( a, q_x(i)) и j(a, q_x(r)) являются неотличимыми.

Так как q^h = F^*( a, qⁱ)= F(a, q^r), то h = h(j(a, q_x(r))).

Следовательно, h = h(j(a,q_j)).

Значит, j(a,q_j), j(a, q_x(j))Î Q_h.

Поэтому состояния j^*( a, q_x(i)) и q_x(h), где q^h =
F^*( a, qⁱ), являются неотличимыми.