База ответов ИНТУИТ

Введение в схемы, автоматы и алгоритмы

<<- Назад к вопросам

Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением (00 + 1)*1?

С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1> ,

С2 = < {0,1}, {q, p, r, s }, q, F2={ s}, Φ2> ,

С3 = < {0,1}, {q, p, r, s, t}, q, F3={ s}, Φ3> ,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

(Отметьте один правильный вариант ответа.)

Варианты ответа
C1 и C2
только C2
все
только C3
C2 и C3
только C1
C1 и C3(Верный ответ)
Похожие вопросы
Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 0(10 +1)*?

С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>,

С2 = < {0,1}, {q, p, r, s }, q, F2={p, r}, Φ2>,

С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, r, s}, Φ3>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Какие из следующих трех автоматов С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>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задан ДКА 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>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ΦA > с программой ΦA: { 0 a →​ 0, 0 b →​ 1, 0 c →​ 1, 1 a →​ 1, 1 b →​ 2, 1 c →​ 1, 2 a →​ 2, 2 b →​ 2, 2 c →​ 1} и гомоморфизм h: {a, b, c}* →​ {0, 1}*: h(a) = 1, h(b) = 01, 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>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задан ДКА 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>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Заданы два НКА:

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a →​ 1, 0 b →​ 3, 1 a →​ 2, 1 b →​ 1, 2 a →​ 1, 2 b →​ 3, 3 a →​ 3, 3b →​ 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 b →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2, q2 b →​ q0

Какие из следующих трех НКА С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> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Заданы два НКА:

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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Заданы два НКА:

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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

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>,

где программы заданы в следующих таблицах.

Пусть задан ДКА 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>,

где программы заданы в следующих таблицах.