Студопедия

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

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

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






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






    Пусть = 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 :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.