Главная /
Введение в схемы, автоматы и алгоритмы /
Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a → 1, 0 a → 2, 0 b → 0, 1 a → 2, 1 b → 1, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a → q1, q1 b → q
Заданы два НКА:
A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA >
с программой
ΦA: 0 a → 1, 0 a → 2, 0 b → 0, 1 a → 2, 1 b → 1, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3
и
B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB >
с программой ΦB: q0 a → q1, q1 b → q0,
q1 a → q2, q2 b → q1
Какие из следующих трех НКА С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, q0, q1, q2}, 0, F3={ q2}, Φ3>
, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).
Правильный ответ:
только
C1
только
C2
только
C3
C1
и C2
C1
и C3
C2
и C3
все
Сложность вопроса
33
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Я провалил экзамен, какого рожна я не углядел данный сайт с ответами по тестам интуит до этого
08 май 2019
Аноним
Если бы не опубликованные подсказки - я бы сломался c этими тестами intuit.
07 сен 2018
Аноним
Спасибо за подсказками по интуит.
06 июн 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # 4. Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {P, S}, ΦA > с программой ΦA: { Q a → R, Q b → P, P b → S, P a → P, R a → R, R b → S, S a → S, S b → R} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = bab, h(1) = aa, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)? С1 = < {0, 1}, { Q, P, R, S }, 0, F1={P, S}, Φ1>, С2 = < {0, 1}, { Q, S }, 0, F2={ S }, Φ2>, С3 = < {0, 1}, { Q, R, S }, 0, F3={ S }, Φ3>, где программы заданы в следующих таблицах. [Большая Картинка]
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв a превосходит количество букв b не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- # Пусть заданы три функции: f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2 Какую функцию F(x1,x2) задает выражение [f; [h; I21 ] [g; [h; I22 ], I22], I22] ?
- # Пусть функция F(x) задана примитивной рекурсией R(1, h(y,z)), где h(y,z) = [2z/z]Чему равно значение F(5)?
- # Пусть машина Тьюринга 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 с помощью операций последовательного и параллельного применения следующим образом: M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?