The Gateway to Computer Science Excellence

0 votes

**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)$.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,397 answers

198,611 comments

105,456 users