Главная /
Введение в схемы, автоматы и алгоритмы /
Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [картинка] Какие из этих машин перево
Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3)
, имеют общий алфавит ленты Σ={ ∧, a, b}
, алфавит состояний Q = { q, p, r, s, !}
, начальное состояние q
, заключительное состояние !
и следующие программы:
Какие из этих машин переводят любую начальную конфигурацию вида q an b
в заключительную конфигурацию ! b an (n ≥ 0 )
?
вопрос
Правильный ответ:
только
M1
только
M2
только
M3
M1
и M2
M1
и M3
M2
и M3
ни одна
Сложность вопроса
15
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Благодарю за подсказками по intuit.
19 апр 2016
Аноним
Зачёт сдал. Мчусь в клуб отмечать экзамен интуит
31 окт 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x+1, (b) x := 0, (c) x := y.
- # [Большая Картинка] Какую булеву функцию реализует эта логическая схема в вершине a?
- # Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?
- # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabbabab, V= babbbabba, U= ababaaab
- # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа x?