Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть задан ДКА A =< {a, b, c}, {0, 1, 2, 3}, 0, F= {2}, ΦA > с программой ΦA: { 0 a → 1, 0 b → 1, 0 c → 0, 1 a → 1, 1 b → 2, 1 c → 2, 2 a → 3, 2 b → 3, 2 c → 2, 3 a → 3, 3 b → 3, 3 c → 3} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 0
Пусть задан ДКА A =< {a, b, c}, {0, 1, 2, 3}, 0, F= {2}, ΦA >
с программой ΦA: { 0 a → 1, 0 b → 1, 0 c → 0, 1 a → 1, 1 b → 2, 1 c → 2, 2 a → 3, 2 b → 3, 2 c → 2, 3 a → 3, 3 b → 3, 3 c → 3}
и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 11, h(c) = ε
Какие из следующих трех автоматов С1 , С2, С3
распознают гомоморфный образ h(LA)
?
С1 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F1={1,2}, Φ1>,
С2 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F2={ 1,2}, Φ2>,
С3 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F3={0,1,2}, Φ3>
,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).
вопросПравильный ответ:
только
C1
только
C2
только
C3
C1
и C2
C1
и C3
C2
и C3
все
Сложность вопроса
94
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Зачёт всё. Мчусь кутить отмечать экзамен интуит
11 апр 2019
Аноним
Я завалил зачёт, какого рожна я не нашёл этот сайт с решениями с тестами intuit до зачёта
05 мар 2018
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # [Большая Картинка] Какую булеву функцию реализует эта диаграмма? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ε ?
- # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x2 + 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 1100 ?
- # В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите Σ, не содержащем символов ∧, * и # , q – начальное состояние) в конфигурацию y* q’ x (q' – заключительное состояние). Пусть Q={ q, s, p, r, q'}∪ {pa | a ∈ Σ} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ? (В текстах программ a – это произвольный символ из Σ, а b - это произвольный символ из Σ ∪ {*, #} ). P1: q b → q b П , q ∧ → s # Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r # → q’ * П. P2: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → r ∧П, pa b → pa b П, pa ∧ → s a Л, r a → r a П , r*→ q’ * П. P3: q a → q a П , q ∧ → s * Л, s b → s b Л, s ∧ → p ∧ П, p a → pa ∧П, p * → q’ * П, pa b → pa b П, pa ∧ → s a Л.