Главная /
Введение в схемы, автоматы и алгоритмы /
В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее MOVE, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее, MOVE, начав работать в конфиг
В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее MOVE
, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее, MOVE
, начав работать в конфигурации вида q a w1 #k#'
(a ∈Σ, w1 ∈Σ*, k ≥ 0
), должна завершить работу в конфигурации ∧kpa'w1
Пусть алфавит ленты MOVE
включает символы из Σ ∪ {a' | a ∈ Σ}∪ {∧, #, #'}
, а алфавит состояний Q= {q, p, r} ∪ {pa | a ∈ Σ}
Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для MOVE
?
(В текстах программ a
и b
– это произвольные символы из Σ
),
P1: q a → pa ∧ П , q a' → p a' Н , pa b → pb a П, pa b' → pb a' П, pa # → r a Л, pa #' → r a' Л, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.
P2: q a → pa ∧ П , pa b → pb a П, pa b' → pb a' П, pa # → r a Л, pa #' → r a' Л, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П.
P3: q a → pa ∧ П , pa b → pa b П, pa # → pa # П, pa #' → r a Л, pa b' → pa b' П, pa ∧ → r a Л, r a → r a Л , r a' → r a' Л , r ∧ → q ∧ П, q # → q ∧ П , q a' → p a' Н.
Правильный ответ:
только
P1
только
P2
только
P3
P1
и P2
P1
и P3
P2
и P3
ни одна
Сложность вопроса
78
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Экзамен прошёл на 5. Спасибо за халяуву
28 сен 2020
Аноним
Я преподаватель! Прямо сейчас сотрите сайт vtone.ru с ответами интуит. Пишу жалобу
31 окт 2016
Аноним
Спасибо за гдз по intuit.
11 июн 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какой язык L является конкатенацией двух языков: L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?
- # Пусть язык L в алфавите {a, b}, состоит из всех слов, которые начинаются на aa и содержат число символов a кратное 3, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = aaa, h(1) = ba, h(2) = ε Какие из следующих трех слов принадлежат прообразу h-1(L) языка L при гомоморфизме h? W1 = 21112, W2 = 20101012, W3 = 00211011
- # Обозначим через minus(x,y) функцию "усеченного" вычитания, равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0] задает функцию (целая часть квадратного корня из x) ?
- # Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф: \begin{array}{lll} q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Л q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П \end{array} В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?
- # Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4) M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 M3 = if Нуль11 then Пуст else Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Умн); Зам(#, *)) enddo; Выб33 endif. M4 = if Нуль11 then Пуст else Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Сум); Зам(#, *)) enddo; Выб33 endif. построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧) Какая из этих машин вычисляет функцию f(x) = xx в унарном кодировании, т.е. переводит вход |x в выход |y, где y = xx (пусть f(0)=0) ?