Главная /
Введение в схемы, автоматы и алгоритмы /
Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 1 (01)*? С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>, С2 = < {0,1}, {q, p, r, s }, q, F2={p, s}, Φ2>, С3 = < {0,1}, {q, p, r, s, t}, q,
Какие из следующих трех автоматов С1
, С2
, С3
распознают язык, представляемый регулярным выражением 1 (01)*
?
С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>
,
С2 = < {0,1}, {q, p, r, s }, q, F2={p, s}, Φ2>
,
С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, s}, Φ3>
,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).
вопросПравильный ответ:
только
C1
только
C2
только
C3
C1
и C2
C1
и C3
C2
и C3
все
Сложность вопроса
56
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень не сложный тест по интуиту.
20 дек 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Чему равна глубина схемы S1, реализующей функцию сложения однобитовых чисел?
- # Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb} Какая из следующих фраз описывает итерацию S* этого языка?
- # Заданы два НКА: 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
- # Пусть задан ДКА 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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]