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

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

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

Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программойΦ: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 →​ 4, 4 a →​ 5, 4 →​ 5, 5 →​ 2Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

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

Варианты ответа
M4 = < {a, b}, {0, 1, 2, 3, 5}, 0, F4={3, 5}, Φ4> с программойΦ4: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 a →​ 3, 3 b →​ 1, 5 a →​ 3,5 b →​ 1(Верный ответ)
M3 = < {a, b}, {0, 1, 2, 3, 5 }, 0, F3={5}, Φ3> с программойΦ3: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 b →​ 1, 5 a →​ 3, 5 b →​ 1
M1 = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F1={3, 4, 5}, Φ1> с программойΦ1: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 1 b →​ 4, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 a →​ 3, 3 b →​ 1, 4 a →​ 5, 5 a →​ 3, 5 b →​ 1
M2 = < {a, b}, {0, 1, 3, 5 }, 0, F2={3, 5}, Φ2> с программойΦ2: 0 b →​ 1, 1 a →​ 2, 1 b →​ 3, 2 a →​ 3, 2 b →​ 1, 3 a →​ 5, 3 a →​ 3, 5 a →​ 3
ни один из выше приведенных автоматов M1, M2, M3, M4
Похожие вопросы
Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={3, 5}, Φ> с программойΦ: 0 b →​ 1, 0 →​ 2, 1 →​ 2, 2 →​ 3, 2 a →​ 1, 3 a →​ 1, 3 b →​ 4, 4 a →​ 5, 5 →​ 3.Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программойΦ: 0 b →​ 1, 0 →​ 2, 1 a →​ 2, 1 b →​ 4, 2 →​ 3, 2 →​ 5, 3 a →​ 4, 3 b →​ 2, 4 →​ 5Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 →​ q, q 1 →​ s, q 1→​ p, p 0 →​ q, p 0 →​ p, s 0 →​ q, s 1 →​ pКакие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F1={p, ps, pq, pqs }, Φ1> с программой Φ1:q 0 →​ q, q 1 →​ ps, p 0 →​ pq, p 1 →​ ∅, s 0 →​ q, s 1 →​ pq, ps 0 →​ pq, ps 1 →​ p, pq 0 →​ pq, pq 1 →​ p, qs 0 →​ q, qs 1 →​pq, pqs 0 →​ pq, pqs 1 →​ ps, ∅ 0 →​∅, ∅ 1 →​∅

M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F2={ p, ps, pq, pqs }, Φ2> с программой Φ2:q 0 →​ q, q 1 →​ ps, p 0 →​ pq, p 1 →​ q, s 0 →​ q, s 1 →​ pq, ps 0 →​ pq, ps 1 →​ p, pq 0 →​ pq, pq 1 →​ ps, qs 0 →​ q, qs 1 →​pq, pqs 0 →​ pq, pqs 1 →​ ps, ∅ 0 →​∅, ∅ 1 →​∅

M3 = < {0, 1}, {q, p, ps, pq, ∅ }, q, F3={ ps, pq, p }, Φ3> с программой Φ3:q 0 →​ q, q 1 →​ ps, ps 0 →​ pq, ps 1 →​ p, pq 0 →​ pq, pq 1 →​ ps, p 0 →​ pq, p 1 →​ ∅, ∅ 0 →​∅, ∅ 1 →​∅

Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 →​ p, q 0 →​ s, p 0 →​ q, p 0 →​ s, p 1 →​ p, s 1 →​ pКакие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, Φ1> с программойΦ1: q 0 →​ ps, q 1 →​ p, p 0 →​ qs, p 1 →​ p, ps 0 →​ qs, ps 1 →​ p, qs 0 →​ ps, qs 1 →​ p

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, qps}, Φ2> с программойΦ2: q 0 →​ ps, q 1 →​ p, p 0 →​ qs, p 1 →​ p, s 0→​ ∅, s 1→​ p, ps 0 →​ qs, ps 1 →​ p, qs 0 →​ ps, qs 1 →​ p, qp 0 →​ ps, qp 1 →​ p, qps 0 →​ qps, qps 1 →​ p, ∅ 0 →​∅, ∅ 1 →​∅.

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, qps }, Φ3> с программойΦ3: q 0 →​ ps, q 1 →​ p, p 0 →​ qs, p 1 →​ p, s 1→​ p, ps 0 →​ qs, ps 1 →​ p, qs 0 →​ qps, qs 1 →​qps, qp 0 →​ ps, qp 1 →​ p, qps 0 →​ qps, qps 1 →​ p. ∅ 0 →​∅, ∅ 1 →​ ∅

Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 →​ p, q 0 →​ s, q 1→​ q, p 0 →​ q, p 0 →​ p, s 1 →​ q, s 1 →​ pКакие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, Φ1> с программой Φ1:q 0 →​ ps, q 1 →​ q, ps 0 →​ pq, ps 1 →​ pq, pq 0 →​ pqs, pq 1 →​ q, pqs 0 →​ pqs, pqs 1 →​ pq

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, pqs }, Φ2> с программой Φ2:q 0 →​ ps, q 1 →​ q, p 0 →​ pq, p 1 →​ q, ps 0 →​ qs, ps 1 →​ pq, pq 0 →​ pqs, pq 1 →​ q, qs 0 →​ ps, qs 1 →​q, pqs 0 →​ pqs, pqs 1 →​ pq, ∅ 0 →​∅, ∅ 1 →​∅

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, pqs }, Φ3> с программой Φ3:q 0 →​ ps, q 1 →​ q, p 0 →​ pq, p 1 →​ q, s 0 →​∅, s 1 →​pq, ps 0 →​ pq, ps 1 →​ pq, pq 0 →​ pqs, pq 1 →​ q, qs 0 →​ ps, qs 1 →​q, pqs 0 →​ pqs, pqs 1 →​ pq, ∅ 0 →​∅, ∅ 1 →​∅

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

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

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= {S}, ΦA > с программой ΦA: { Q a →​ R, Q b →​ P, P b →​ P, P a →​ R, R a →​ Q, R b →​ S, S a →​ R, S b →​ S} и гомоморфизм h: {0, 1, 2}* →​ {a, b}*: h(0) = bab, h(1) = aba, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

С1 = < {0, 1}, { Q, P, R, S }, 0, F1={S}, Φ1>,

С2 = < {0, 1}, { Q, R, S }, 0, F2={ S }, Φ2>,

С3 = < {0, 1}, { Q, P, 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>,

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