Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть машина Тьюринга 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
;
с помощью операций последовательного и параллельного применения следующим образом:
M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); Зам(#, *); Сум
Какую из следующих арифметических функций f(x)
(при унарном кодировании аргумента и результата) вычисляет M
?
вопрос
Правильный ответ:
f(x) = 2x2 + 2x
f(x) = x2 + x
f(x) = 2x2 + x
f(x) = x2 + 2x
ни одну из выше перечисленных
Сложность вопроса
50
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Кто ищет данные вопросы inuit? Это же совсем для даунов
13 май 2020
Аноним
Спасибо за гдз по интуит.
04 сен 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = ((a ∧ ¬b) ∨ ¬b) ∨ ¬ (b∨ c) ? [Большая Картинка]
- # Пусть задана логическая схема S=(V, E) : V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(∨),g(∨),h(∨), i(∧), k(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, d), (a, g), (b, e), (b, f), (b, g), (c, f), (d, h), (e, h), (f,k), (g,i), (h, i), (i, k) }. Какую булеву функцию реализует схема S=(V, E) в вершине k? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)
- # Пусть задан конечный автомат - преобразователь A = <ΣX ={0, 1} ΣY= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?
- # Какой язык L является конкатенацией двух языков: L1= {ε, b, ab, abba} и L2= { a, b, ba}?
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на cac и содержат подслово bcb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 0, h(b) = 11, h(c) = ε ?