GATE CSE 2020 | Question: 8

Question

Consider the following statements.

1. If $L_1 \cup L_2$ is regular, then both   $L_1$ and $L_2$ must be regular.
2. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

• A. Ⅰ only
• B. Ⅱ only
• C. Both Ⅰ and  Ⅱ
• D. Neither Ⅰ nor  Ⅱ

Comments

https://www.youtube.com/watch?v=tpPAYwgZf2o&t=150s

---

$\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{  , With ALL Variations:}}$

https://youtu.be/tpPAYwgZf2o

Answer 1

Keeping $L_2$ as $\Sigma^*,$ what ever may be $L_1,$, we get a Regular language.

So, statement I is wrong.

If regular languages are closed under infinite union, then $L=\{a^n.b^n | n>0 \}$ must be regular as it is equal to $\{ab\} \cup \{aabb\} \cup \{aaabbb\} \cup \ldots$

So, statement II is wrong.

Option D is correct.

Comments

Correct me if wrong, a^n b^n is not regular

---

a^n b^n is regular for n=0, it is simple as a*b*, which is regular.

a^n b^n is not regular for n>0. We need infinite memory for a^n b^n | n>0.

---

perfect solution, I too thought like this...

Answer 2

L1 is $\sum$*, L2 is string having equal number of a and b. 

L1 U L2 is $\sum $* , which is regular, but L2 is CFL.

2 

Regular language is closed under finite union but not closed under infinite union. 

See: https://gateoverflow.in/3078/proof-regarding-infinite-union-intesection

So D is correct.

 

Answer 3

Answer : D

I. is false since (a+b)* is regular but  L1 = (a+b)* and L2 ={$a^{n} b^{n} | n>=0$}

II. is false since  ab, aabb, aaabbb ........  (all of them is regular language) make language DCFL where each one of them is regular

Comments

Better and simple explanation to the question than rest above.