GATE 2019 CS – Question 41
Which one of the following languages over $\Sigma=\{a,b\}$ is NOT context-free?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $\{wa^nw^Rb^n\mid w\in\{a,b\}^*,\ n\ge0\}$
Explanation
**(A)** $\{ww^R\}$: a PDA pushes $w$ and then pops while reading $w^R$, guessing the middle. Context-free.
**(B)** $\{wa^nb^nw^R\}$: push $w$, then match $a^nb^n$ with a counter on top of the stack, then pop $w$ while reading $w^R$. The nested structure $w(\,a^nb^n\,)w^R$ is context-free.
**(D)** $\{a^nb^i\mid i\in\{n,3n,5n\}\}$ is a union of the three context-free languages $\{a^nb^n\}$, $\{a^nb^{3n}\}$, $\{a^nb^{5n}\}$ (push 1, 3 or 5 symbols per $a$). Context-free.
**(C)** $\{wa^nw^Rb^n\}$: here $w$ must be matched with $w^R$, and $a^n$ must be matched with $b^n$. The $a^n$ is read first (after $w$), then $w^R$, then $b^n$. A single stack would have to keep $w$ on top of $a^n$ while reading $w^R$ and, afterwards, have the count $n$ available for $b^n$, but popping $w$ to check $w^R$ requires the $a$'s not to be in the way. The two dependencies **cross** instead of nesting, and the pumping lemma for CFLs confirms that this language is not context-free.