in Theory of Computation retagged by
13,312 views
17 votes
17 votes

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?

  1. Ⅰ only
  2. Ⅱ only
  3. Both Ⅰ and  Ⅱ
  4. Neither Ⅰ nor  Ⅱ
in Theory of Computation retagged by
by
13.3k views

2 Comments

3
3

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

https://youtu.be/tpPAYwgZf2o

3
3

3 Answers

24 votes
24 votes
Best answer
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.
edited by

3 Comments

Correct me if wrong, a^n b^n is not regular
1
1
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.
1
1
perfect solution, I too thought like this...
0
0
2 votes
2 votes

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.

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.

 

1 vote
1 vote
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

1 comment

Better and simple explanation to the question than rest above.
0
0
Answer:

Related questions