The Gateway to Computer Science Excellence
0 votes
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)$.

in Theory of Computation by Boss (15.4k points) | 18 views

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,397 answers
198,611 comments
105,456 users