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

Not getting last one...

---

@Pyuri If we concatenate any set with $\phi$ we get $\phi$ and $\phi$ is regular.

@Praveen+Saini There is a problem in first proof. Regular set is not closed under infinite union. So, we must reduce infinite union to infinite intersection (not the other way) and show that infinite intersection is also not closed as complement of regular set is regular.

---

@arjun

$L1 \cap L2 \cap L3 \cap L4 \cap \dots$

if $L1 \cap L2 \cap L3 \cap L4 \cap \dots$ is regular then it means $(L1' \cup L2' \cup L3' \cup L4' \cup \dots)'$ is regular, then its complement $L1' \cup L2' \cup L3' \cup L4' \cup \dots$ must be regular, but it is not. then it means $L1 \cap L2 \cap L3 \cap L4 \cap \dots$ is not regular.

is that correct ?

---

yes, thats fine :)

---

@praveen saini, in the third one,

L = {} is regular and M be non-regular like {0ⁿ1ⁿ | n>0}

then, can L.M becomes {0ⁿ1ⁿ}???????

concatenation means appending the second string to the end of the first string right??? in that case L.M is not regular. right???

please Clarify this????

---

@vamsi Concatenation means appending a string to the end of other. But there are no string in $\{\}$ and so concatenation results in nothing. i.e., nothing concatenated with anything is nothing (like multiplication by 0). If we concatenate empty string $\epsilon$ with any string, we get the same string (like multiplication by 1).

---

yes sir. so in the above case, L.M becomes {0ⁿ1ⁿ} which is not regular. is it correct??

---

no. Concatenation is with strings of $\{\}$ which gives $\{\}$. It is not with strings from $\{\epsilon\}$.

---

ooookkkkk..... got it sir... thank you....

---

Concatenation of (a+b)* and {a^nb^n | n>=0}?

---

(a+b)*

---

@Praveen sir concatenation of  L=(a+b)* and M={a^nb^n | n>=0} two strings L and M will be

L.M = (a+b)*

because L = (ϵ, a, b, aa, ab, ba, bb, .....) * M=(ϵ,ab, aabb, aaabbb)

result will be (a+b)*  may i right?

---

No ,
you are missing epsilon $\epsilon$, otherwise language will be differ.

---

Yes sir, because i do' t know how to add epsilon symbol in this sheet.

---

@Praveen sir

(iii) if L={epsilon} and M={a^nb^n} then L.M is not regular

and if L=phi then L.M is regular.

so L.M is not necessarily regular. I think option iii is true

---

you are contradicting your statement

---

got my mistake sir :D

---

L={a}

M= a^nb^n

is L.M regular?

it will be a^n+1 b^n

---

if  L={ab} i.e a regular lang

  M={a^n b^n  | n>0}  i.e. a CFL lang

L.M ={abab,abaabb,abaaabbb,...........}

so L.M is not regular always

---

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.