UGC NET CSE | October 2020 | Part 2 | Question: 27

Question

Consider $L=L_1 \cap L_2$ where

$L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$

$L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$

Then, the language $L$ is

• A. Recursively enumerable but not context free
• B. Regular
• C. Context free but not regular
• D. Not recursive

 

Comments

Intersection of CFL and Regular language is Context-Free Language. But not Regular. So option C.

Answer 1

L1 is CFL (comparison possible by single stack)   and L2 is regular (DFA is there )  so by Theorem of regular intersection

L=L1 ∩L2 must be CFL  so option C

Comments

Is the first Language DCFL, Sir ?

---

yes it is dcfl as we know deterministically what to do on rreading input string

---

sir L2 is not regular .observe 2^k we can not draw finite automata for this.

 

---

whats the problem with 2^k    , k >=0   simply a loop over alphabet 2

Answer 2

The language L1 $ \cap $ L2  is $ 0^{m} 1^{m} 2 $ which is not regular by pumping lemma. However you can easily create a CFL for this.

$ S’ \rightarrow S 2 $

$S \rightarrow 0 S 1, \epsilon $

Hence the answer is C.

Comments

Typo. It should be an intersection.