18 views

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)$. we claim that $h (L)$ is regular.

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

| 18 views