The GATE Grind

GATE 2019 CS – Question 41

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

Which one of the following languages over $\Sigma=\{a,b\}$ is NOT context-free?

  1. $\{ww^R\mid w\in\{a,b\}^*\}$
  2. $\{wa^nb^nw^R\mid w\in\{a,b\}^*,\ n\ge0\}$
  3. $\{wa^nw^Rb^n\mid w\in\{a,b\}^*,\ n\ge0\}$
  4. $\{a^nb^i\mid i\in\{n,3n,5n\},\ n\ge0\}$

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.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →