Главная /
Введение в схемы, автоматы и алгоритмы /
Три машины Тьюринга 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 a2n (n ≥ 0 )
?
вопрос
Правильный ответ:
только
M1
только
M2
только
M3
M1
и M2
M1
и M3
M2
и M3
ни одна
Сложность вопроса
91
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Большое спасибо за тесты по intuit.
07 сен 2020
Аноним
Я завалил сессию, какого рожна я не увидел данный сайт с всеми ответами по интуит до этого
26 май 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x+1, (b) x := 0, (c) x := y.
- # [Большая Картинка] Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
- # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a → 1, 0 b → 3, 1 a → 3 1 b → 2, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a → q0, q0 b → q1, q1 a → q1, q1 a → q2 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв a превосходит количество букв b не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- # Пусть структурированная программа P: x:= y+1; z := x+1; y := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии σ : σ(x) = 2, σ(y) =3, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?