Formal Languages and Automata:

In the proof of Theorem 4.3, shows that h(r) is a regular expression. Then show that h(r) denotes h(L)

The orem 4.3 Let h be a homomorphism IfL is a regular language, then its homomorphic image h (L) is also regular. The family of regular languages is therefore closed under arbitrary homomorphisms. Proof: Let L be a regular language denoted by some regular expressionr. We find h (r) by substitutingh (a) for each symbol ae2ofr. It can be shown directly by an appeal to the definition of a regular expression that the result is a regular expression. It is equally easy to see that the resulting expression denotes h (L). All we need to do is to show that for every w e L (r), the corresponding /h ( is in L (h (r)) and conversely that every u in L (h ( there is aw in L, such that u-h (w). Leaving the details as an exercise, we claim that h (L) is regular.- De finition 4.2 Let L, and L2 be languages on the same alphabet. Then the right quotient ofL, with L2 is defined as ?1/L2-(x : xy L1 for some y L2) To form the right quotient of L1 with L2. we take all the strings in L ?2. Every such string, after removal of this suffix, belongs to L/L). that have a suffix belonging to The orem 4.3 Let h be a homomorphism IfL is a regular language, then its homomorphic image h (L) is also regular. The family of regular languages is therefore closed under arbitrary homomorphisms. Proof: Let L be a regular language denoted by some regular expressionr. We find h (r) by substitutingh (a) for each symbol ae2ofr. It can be shown directly by an appeal to the definition of a regular expression that the result is a regular expression. It is equally easy to see that the resulting expression denotes h (L). All we need to do is to show that for every w e L (r), the corresponding /h ( is in L (h (r)) and conversely that every u in L (h ( there is aw in L, such that u-h (w). Leaving the details as an exercise, we claim that h (L) is regular.- De finition 4.2 Let L, and L2 be languages on the same alphabet. Then the right quotient ofL, with L2 is defined as ?1/L2-(x : xy L1 for some y L2) To form the right quotient of L1 with L2. we take all the strings in L ?2. Every such string, after removal of this suffix, belongs to L/L). that have a suffix belonging to