GATE CSE 2009 | Question: 40

Question

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below:

$L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$

$L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$

Then $L$ is

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

Comments

DCFL are closed under intersection with regular languages.

---

sir,  when L1 is cfl=>  Because Read input a, push into stack; seen ‘b’ pop ‘a’; seen c skip, again Read input a, push into stack; seen ‘b’ pop ‘a’; using (dpda)and L2 is Regular Because, easily construct DFA =>first take FOUR states to construct dfa  1,2,3,d; seen ‘a’ looping  on 1, other than ‘a’ goto dead state, seen b goto the state 2 any number of b looping on 2, if ‘a’ come to here then go to dead state, if ‘C’ is coming then go to state 3, in here a or b come goto dead state.  L=L1 intersection L2. so, L is cfl.

---

@Ajitgate21 When actual languages are given, it’s better not to use closure property but to work out the language itself and check what type of language it is.

Answer 1

Intersection of CFL and regular is always CFL. so option C

Answer 2

option c