Введение в схемы, автоматы и алгоритмы
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на cac и содержат подслово bcb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где
h(a) = 0, h(b) = 11, h(c) = ε ?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>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).