ISI2015-PCB-CS-5a

Question

Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular.

Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 \cup L_2$ is regular.

Comments

Consider  non regular  languages  L1={a^n | n is a prime no.}   and  L2={a^n | n is a composite no.}

L1 U L2 ={a^n|n>1} which is regular

---

According to me, the above example is perfectly correct.

Do you think the same?

@techbd123

---

I also think the same.

---

Thanks!!

Answer 1

Consider a language $ L_1=\left \{ a^{n} b^{n} \mid n\geq 0 \right \}$ is a non regular language .

And take another language $ L_2={L_1}^{c}$  which is also non regular .(Since regular set is  closed under complementation.)

As we know the union of any language and its complement is $\Sigma^*$^.

So, $L_1\cup L_2=\Sigma^*$ and this is regular.

Comments

I still did not understand the significance of writing - (Since regular set is  closed under complementation.). Could some one try to elaborate a bit more please?

---

L1={$a^{m}$ $b^{n}$∣m=n; m,n≥0}

L2={$a^{m}$ $b^{n}$∣m!=n; m,n≥0}

L1 U L2 = {a*b*}

Please correct me if I'm wrong. :)

---

L2 is not exact complement of L1 in your example

Answer 2

Consider a language L1={aⁿb^m ,n≥m for all +ve integer} is a non regular language .

Consider a language L2={aⁿb^m ,m≥n for all +ve integer} is a non regular language .

L1∪L2 gives you a⁺b⁺ is regular.

Answer 3

Let Σ={a}

Let L1 ={a^p| p is prime}   and L2 = {a^q| q is not prime}

L1UL2 =  Σ*   – Regular

Answer 4

Consider any non-regular language, call it L1 , and now consider L2 as complement of L1, L2 will also be non-regular by closure property, now L1 $L1 \bigcup L2$ is always regular ( equal to sigma*)