Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {R}, ΦA > с программой ΦA: { Q a → P, Q b → Q, P b → P, P a → R, R a → Q, R b → S, S a → S, S b → S} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = aba, h(1) = aa, h(2) = ε Какие из следующих
Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {R}, ΦA >
с программой ΦA: { Q a → P, Q b → Q, P b → P, P a → R, R a → Q, R b → S, S a → S, S b → S}
и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = aba, h(1) = aa, h(2) = ε
Какие из следующих трех автоматов С1
, С2
, С3
распознают гомоморфный прообраз h-1(LA)
?
С1 = < {0, 1}, { Q, P, R, S }, 0, F1={ R }, Φ1>,
С2 = < {0, 1}, { Q, P, R, S }, 0, F2={ R }, Φ2>,
С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ R }, Φ3>
,
где программы заданы в следующих таблицах.
вопросПравильный ответ:
только
C1
только
C2
только
C3
C1
и C2
C1
и C3
C2
и C3
все
Сложность вопроса
87
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Спасибо за решениями по интуит.
26 окт 2017
Аноним
Если бы не опубликованные ответы - я бы сломался c этими тестами интуит.
08 фев 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть множество A = { (x, y) | y = x2 }, B = { 2n | n ∈ N }. Какие из следующих функций осуществляют сведение A ≤m B ? (В выражениях ниже sqr(y) обозначает целую часть квадратного корня из y, sg(0) =0 и sg(n) = 1 при n > 0).
- # Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- # Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?
- # Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ΦA > с программой ΦA: { 0 a → 1, 0 b → 0, 0 c → 1, 1 a → 2, 1 b → 1, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 1, h(c) = ε Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)? С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, Φ1>, С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, Φ2>, С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами: F(0) = 0, F(1) = 1, F(y+2) = F(y) + F(y+1) +1. Положим G(y) = c2(F(y), F(y+1)). Так как F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.