Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

1) () = () Y (a, F*(, q i);

2) () = () y(a, j*(, q x(i))).

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

 

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



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

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

Y(a, F*(, q i) = Y(a, q r) = y(a, qx (r)) = y(a, q j)= = y(a, j*(, qx (i))).

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

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

 

Так как q j и qx ( r ) Î Q r, то состояния j*( a, qx (i)) и j(a, qx ( r )) являются неотличимыми.

 

Так как q h = F*( a, q i)= F(a, q r), то h = h (j (a, qx (r))).

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

Значит, j(a, q j), j(a, qx (j)Qh .

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.