If L is a language on Σ, then its homomorphic image is defined as
Example 4.2
Let Σ = {a, b, c} and Γ = {a, b, c,} define h by
Then h (aba) = abbbcab. The homomorphic image of L = {aa, aba} is the
language h (L) = {abab, abbbcab}.
If we have a regular expression r for a language L, then a regular expression
for h (L) can be obtained by simply applying the homomorphism to each Σ
symbol of r.
Example 4.3
Take Σ = {a, b} and Γ = {b, c, d}. Define h by
If L is the regular language denoted by
then
denotes the regular language h (L).
The general result on the closure of regular languages under any
homomorphism follows from this example in an obvious manner.