Индуктивный переход

Базис индукции

" a Î A ^*( (a) = Y(a, q ⁱ)= y(a, q _x(i)) = (a)).

При этом j(a, q _x(i)) и q _{x( r )} -неотличимые состояния автомата Â, где q ^r = F^*(a, q ⁱ).

Индуктивное предположение

" Î A ^*(| | £ k Þ () = ()).

При этом j^*(, q _x(i)) и q _{x( r )} - неотличимые состояния автомата Â, где q ^r = F ^*(, q ⁱ).

Пусть = 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 ⁱ), являются неотличимыми.

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