GATE 2015 CS (CS3) – Question 44
Which languages are context-free? $L_1=\{a^mb^na^nb^m:m,n\ge1\}$; $L_2=\{a^mb^na^mb^n:m,n\ge1\}$; $L_3=\{a^mb^n:m=2n+1\}$.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) L₁ and L₃ only
Explanation
L₁ has nested dependencies: an outer stack match handles the first/last blocks and an inner match handles the middle blocks, so it is context-free. L₃ uses a two-for-one stack comparison plus one extra a and is context-free. L₂ requires crossing equalities between separated blocks. Applying the context-free pumping lemma to a^p b^p a^p b^p, a pumpable window of length at most p touches at most two adjacent blocks and cannot change a block together with its separated equal partner; pumping violates an equality. Thus L₂ is not context-free, so L₁ and L₃ only, B.