Наконец, покажем, что прообраз ЯРВ при отображении недетерминированной последовательностной машиной может не быть ЯРВ. Недетерминированная ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций


Наконец, покажем, что прообраз ЯРВ при отображении недетерминированной последовательностной машиной может не быть ЯРВ. Недетерминированная последовательностная машина есть шестерка U ( Q, 2, А, М, R, Q0), где Q - конечное множество состояний, 2 - входной, а А - выходной алфавиты, М - функция, отображающая Q X 2 в 2Q, R - отображение Q X 2 в Л и Qo s Q - множество начальных состояний. U действует очевидным способом.

(cкачать страницу)

Смотреть книгу на libgen

Наконец, покажем, что прообраз ЯРВ при отображении недетерминированной последовательностной машиной может не быть ЯРВ. Недетерминированная последовательностная машина есть шестерка U ( Q, 2, А, М, R, Q0), где Q - конечное множество состояний, 2 - входной, а А - выходной алфавиты, М - функция, отображающая Q X 2 в 2Q, R - отображение Q X 2 в Л и Qo s Q - множество начальных состояний. U действует очевидным способом.