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