edited by
4,831 views
22 votes
22 votes

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?

  1. true, false, true.
  2. false, false, true.
  3. true, false, true.
  4. false, false, false.
  5. true, true, true.
edited by

3 Answers

Best answer
35 votes
35 votes
  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$

edited by
1 votes
1 votes

(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)

1 votes
1 votes

Answer is B .

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

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

               M=anbn 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.

Answer:

Related questions