-2
$\begingroup$

I have to prove that the set of rational or regular languages is closed by morphism on their alphabet.

i.e. that the image of a rational language by a morphism is still rational.

h being a morphism from Σ to Σ', my idea is to start with an automaton A and to construct an automaton A' wich recognizes the language h(L(A)).

I use the same initial and final states then, for any transition (q, a, q') in A, I consider 3 cases :

1) if h(a) = ε I add the states q, q' (if they do not already exist in A') and an ε transition (q, ε, q')

2) if h(a) = b ∈ Σ', I add the states q, q' (if they do not already exist in A') and a transition (q, b, q')

3) if h(a) = b_1b_2...b_n ∈ Σ'*, I add the states q, q' (if they do not already exist in A') plus n-1 new states and n transitions from (q, b_1, q_1) to (q_{n-1}, b_n, q')

Then it's "easy" to prove that h(L(A)) is included in L(A') following the construction steps, however I'm struggling to prove the converse, i.e. that L(A') is included in h(L(A))

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.