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?

$\{ww^R\mid w\in\{a,b\}^*\}$
$\{wa^nb^nw^R\mid w\in\{a,b\}^*,\ n\ge0\}$
$\{wa^nw^Rb^n\mid w\in\{a,b\}^*,\ n\ge0\}$
$\{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 pushdown automaton can match $ww^R$ (A), match $w$ with $w^R$ around a nested $a^nb^n$ (B), and pick one of three options for $i$ non-deterministically (D). In C the $w^R$ and $b^n$ are interleaved (crossing dependencies), which needs two independent counters, so C is not context-free.