Theorem 4.3
Let h be a homomorphism. If L 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 expression r. We
find h (r) by substituting h (a) for each symbol a ∈ Σ of r. 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 ∈ L (r), the corresponding h
(w) is in L (h (r)) and conversely that every υ in L (h (r)) there is a w in L, such
that υ = h (w). Leaving the details as an exercise, we claim that h (L) is regular.
Definition 4.2
Let L 1 and L 2 be languages on the same alphabet. Then the right quotient of
L 1 with L 2 is defined as
To form the right quotient of L 1 with L 2 , we take all the strings in L 1 that
have a suffix belonging to L 2 . Every such string, after removal of this suffix,
belongs to L 1 /L 2 .
Example 4.4
If
and