self doubt: TOC

Question

is union of regular language and context free language always regular?

Comments

take a regular language over input alphabet set {a, b} as L1= $\{ab\} $

take a CFL over input alphabet {a, b} as L2 = $\{a^nb^n | n >0\}$ where n is a positive integer.
Now, union of both will be $\{a^nb^n | n >0\}$which is CFL but not regular.

---

Thanks brother.. :)

---

No, Union of regular language and CFL is not regular.

Answer 1

Suppose there are two CFL's L1 and L2. $\because$ they are CFL's they have equivalent CFG's. They have a start symbol as well, say S1 and S2. Now create a new production S->S1|S2. As you can see now you have a grammar for the language $L1\cup L2$ of two languages. Therefore you have a CFL for it as well. You also know that every regular language is also context free. Therefore union of regular and context free languages is closed under union.