Какие из следующих трех конечных автоматовAi = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые заканчиваются на b и содержат число букв a , кратное 3 ?
Введение в схемы, автоматы и алгоритмы
Какие из следующих трех конечных автоматовAi = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ?
Какие из следующих трех конечных автоматовAi = < {a,b}, {0, 1, 2, 3}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на a и содержат четное число букв b ?
С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> ,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).
С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>,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).
С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>,
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).
Пусть задан ДКА 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}, 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}, {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>,
где программы заданы в следующих таблицах.