Главная /
Введение в схемы, автоматы и алгоритмы /
В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов ∧, *
В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE
, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y
(x
и y
– слова в алфавите Σ
, не содержащем символов ∧
, *
и #
, q
– начальное состояние) в конфигурацию
y* q’ x
(q'
– заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {pa | a ∈ Σ}
– множество состояний CHANGE
. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE
?
(В текстах программ a – это произвольный символ из Σ, а b
- это произвольный символ из Σ ∪ {*, #}
).
P1: q b → q b П , q ∧ → s # Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r # → q’ * П.
P2: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r*→ q’ * П.
P3: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → q’ * П, pa b → pa b П, pa ∧ → s a Л.
Правильный ответ:
только
P1
только
P2
только
P3
P1
и P2
P1
и P3
P2
и P3
ни одна
Сложность вопроса
87
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Я сотрудник деканата! Прямо сейчас заблокируйте этот ваш сайт с ответами по интуит. Не ломайте образование
26 апр 2019
Аноним
Зачёт всё. Мчусь кутить отмечать халяву с тестами интуит
18 сен 2016
Аноним
Пишет вам помощник профессора! Срочно удалите сайт с ответами с интуит. Я буду жаловаться!
02 апр 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Чему равна глубина схемы S1, реализующей функцию сложения однобитовых чисел?
- # Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- # Пусть регулярное выражение (ab)*a определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
- # Пусть структурированная программа P: x:= y+1; y := z+1; z := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии σ : σ(x) = 3, σ(y) =4, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?
- # Обозначим через minus(x,y) функцию "усеченного" вычитания, равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y, i) выражение μi [ f(x,y,i)= 0] задает функцию F(x,y) = [ y/x ] (целая часть частного от деления y на x) ?