TIFR CSE 2014 | Part B | Question: 12

Question

Consider the following three statements:

1. Intersection of infinitely many regular languages must be regular.
2. Every subset of a regular language is regular.
3. If $L$ is regular and $M$ is not regular then $L ∙ M$ is necessarily not regular.

Which of the following gives the correct true/false evaluation of the above?

• A. true, false, true.
• B. false, false, true.
• C. true, false, true.
• D. false, false, false.
• E. true, true, true.

Comments

i think 1st and 2nd are false .

and the 3rd one dot means ??

---

I think  dot means intersection

---

hmm It is concatenation :)

Answer 1

1. False
   Regular Languages are not closed under Infinite Union and Intersection 
   $L_1 \cup L_2 \cup L_3 \cup L_4 \cup \dots $
   For example :
   ${ab} \cup {aabb} \cup {aaabbb} \cup {aaaabbbb} \cup \dots$
   $=\{ a^nb^n, n\geq 1\}$ which is not regular
   So, Infinite Union is not closed 
   $L_1 \cap L_2 \cap L_3 \cap L_4 \cap \dots$
   $= (L_1' \cup L_2' \cup L_3' \cup L_4' \cup \dots)'$
   As Infinite Union is not closed, Infinite Intersection is also not closed 
2. False. 
   $a^*b^*$ is regular 
   its subset $a^nb^n, n\geq 1$  is not regular 
   $a^*$ is regular
   $a^p , p$ is prime, is not regular 
3. False 
   $L = \{\}$  is regular 
   M be non-regular like $\{0^n1^n \mid n > 0 \}$. 
   $L.M = \{\}$ , is regular 

Correct Answer: $D$

Comments

What would be the case with "Infinite concatenation?" Are regular language closed under infinite concatenation ?

---

L= epsilon  is regular
M= {a^n b^n /n>=0 }  is non-regular
L.M = epsilon.(a^n b^n) = a^n b^n   is non-regular

So iii is true , right??

---

I did the same mistake. It’s necessarily not regular,  and not, not necessarily regular. 

Answer 2

(i) False.Infinite union or intersection both are not closed under regular language.

(ii)False . a^n b^n is subset of a*b* , but a^n b^n not regular

(ii)True . Let L=regular ,M=CFL ,then L.M=CFL

So, ans (B)

Comments

L.M = CFL doesn't mean that it will L.M will necessarily be not regular. Regular Languages are subset of CFL.

Answer 3

Answer is B .

and the reason for (iii) L.M necessarily regular is ,

consider ..L=(a+b)^*  which is regular ,

               M=aⁿbⁿ which is CFL and not regular .

so concatinating these two strings , the resulting string will be regular which is nothing but (a+b)*.

So the word necessarily is important in this question.