Главная /
Введение в схемы, автоматы и алгоритмы /
Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ
Предположим, что в некоторой конфигурации машины Тьюринга M
на ленте записано слово w
в алфавите Σ
, не содержащем символов ∧
и *
, но головка "заблудилась" – она наблюдает символ ∧
и не знает левее или правее слова w находится.
Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧k w
или w∧k q ∧
(k > 0
) переведут в конфигурацию q'w
?
(В текстах программ a
– это произвольный символ из Σ
, используемые состояния: q, q', l, r, l1, r1 , l2 , r2, l3, r3, l4
)
P1: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 a→ l2 a Л, l2 ∧→ q'∧ П, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н.
P2: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 ∧→ l2∧ П, l2 *→ l3∧ Л, l3 ∧→ l3∧ Л, l3 a→ q'a Н,
r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л,
r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н.
P3: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 ∧→ l2∧ П, l2 *→ l3∧ Л, l3 ∧→ l3∧ Л, l3 a→ l4 a Л,
l4 a→ l4 a Л, l4 ∧→ q'∧ П, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л,
r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н.
Правильный ответ:
только
P1
только
P2
только
P3
P1
и P2
P1
и P3
P2
и P3
ни одна
Сложность вопроса
76
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Зачёт в студне отлично. Мчусь в бар отмечать халяву с тестами интуит
16 мар 2016
Аноним
Кто ищет данные вопросы по интуит? Это же элементарно
28 ноя 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ? P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* ) P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* ) P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ) В этих определениях участвуют следующие простые машины Тьюринга: Копa – копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст – не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;+1 – прибавляет 1 к аргументу: |x ⇐ |x+1
- # Пусть задана логическая схема 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.
- # Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
- # Заданы два НКА: 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}, состоит из всех слов, которые начинаются на 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