recategorized by
2,172 views
2 votes
2 votes

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

  1. Recursively enumerable but not context free
  2. Regular
  3. Context free but not regular
  4. Not recursive

 

recategorized by

2 Answers

2 votes
2 votes
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
2 votes
2 votes
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.
edited by
Answer:

Related questions