Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w; Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Сум - складывает два аргумента
Пусть машина Тьюринга M
построена из следующих простых машин Тьюринга:
Копa
–копирует вход после разделительного символа a : w ⇐ w a w
;
Зам(a, b)
– заменяет первое слева вхождение символа a
на b
: w1a w2 ⇐ w1 b w2 ( a ∉ w1 )
;Сум
- складывает два аргумента в унарной системе: |x * |y ⇐ |x+y
;Умн
- умножает два аргумента в унарной системе: |x * |y ⇐ |xy
;Пуст
- не изменяет аргумент: w ⇐ w
с помощью операций последовательного и параллельного применения следующим образом:
Зам(a, b)
– заменяет первое слева вхождение символа a
на b
: w1a w2 ⇐ w1 b w2 ( a ∉ w1 )
;Сум
- складывает два аргумента в унарной системе: |x * |y ⇐ |x+y
;Умн
- умножает два аргумента в унарной системе: |x * |y ⇐ |xy
;Пуст
- не изменяет аргумент: w ⇐ w
M = Коп# ; par#( Коп* ; Умн, Пуст ); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум
f(x)
(при унарном кодировании аргумента и результата) вычисляет M
?
вопрос
Правильный ответ:
f(x) = 2x2 + 2x
f(x) = x2 + x
f(x) = 2x2 + x
f(x) = x2 + 2x
ни одну из выше перечисленных
Сложность вопроса
50
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень простецкий решебник по интуиту.
16 окт 2018
Аноним
Это очень легкий решебник по интуиту.
23 июн 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ? (а) рефлексивность: A ≤m A ,(b) симметричность: A ≤m B ⇔ B ≤m A,(с) транзитивность: A ≤m B и B ≤m C ⇐ A ≤m C .
- # [Большая Картинка] Какую булеву функцию реализует эта логическая схема в вершине a ?
- # Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(∧), f(∧),g(¬),h(¬), i(∧), k(∧), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, h), (b, f), (c, e), (c, g), (d, f), (e, i), (f ,i), (f ,k), (g,, k), (h,e),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: X = ¬X; h = ¬X; X = ¬X; Z = ¬Z; g = ¬Z; X = X ∧ Z; X = X ∧ Z; e = h ∧ Z; Z = ¬Z; Y = Y ∧ V; f = Y ∧ V; V = Y ∧ V; Y = Y ∧ X; k = f ∧ g; V = X ∧ V; Z = Y ∧ Z; i = e ∧ f; Y = V ∧ Z; Z = Y ∨ Z. Z = i ∨ k. Z = Y ∨ V.
- # Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={3, 5}, Φ> с программой Φ: 0 b → 1, 0 → 2, 1 → 2, 2 → 3, 2 a → 1, 3 a → 1, 3 b → 4, 4 a → 5, 5 → 3. Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
- # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конецP2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конецP3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все