Я должен доказать, что множество рациональных или регулярных языков замкнуто морфизмом в их алфавите.
т.е. что образ рационального языка по морфизму все еще рациональн.
h, будучи морфизмом от Σ к Σ ', моя идея состоит в том, чтобы начать с автомата A и построить автомат A, который распознает язык h (L (A)).
Тогда я использую те же начальные и конечные состояния для любого перехода (q, a, q ') в A, я рассматриваю 3 случая:
1) если h (a) = ε, я добавляю состояния q, q '(если они еще не существуют в A') и ε-переход (q, ε, q ')
2) если h (a) = b ∈ Σ ', я добавляю состояния q, q' (если они еще не существуют в A ') и переход (q, b, q')
3) если h (a) = b_1b_2 ... b_n ∈ Σ '*, я добавляю состояния q, q' (если они еще не существуют в A ') плюс n-1 новых состояний и n переходов из (q, b_1, q_1) - (q_ {n-1}, b_n, q ')
Тогда "легко" доказать, что h (L (A)) включено в L (A ') после этапов построения, однако я изо всех сил пытаюсь доказать обратное, то есть, что L (A') включено в ч (L (A))