GATE CS 2019 Q31 — Context-free Grammars and Push-down Automata

To determine which language is NOT context-free, let us analyze each option:

• Option A: $\{ww^R \mid w \in \{a, b\}^*\}$ is a classic context-free language (even-length palindromes) generated by the CFG: $S \to aSa \mid bSb \mid \epsilon$.
• Option B: $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ has nested dependencies. The outer part $w \dots w^R$ and the inner part $a^n b^n$ can both be processed using a single stack in LIFO order. It is generated by the CFG: $$S \to aSa \mid bSb \mid A$$ $$A \to aAb \mid \epsilon$$ Thus, it is context-free.
• Option C: $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ contains overlapping (cross-serial) dependencies. We must match $w$ with $w^R$, and $a^n$ with $b^n$. Since $w^R$ appears before $b^n$, a single stack cannot maintain the count of $a^n$ while simultaneously matching $w$ with $w^R$. This requires two independent comparisons, which is beyond the capability of a Pushdown Automaton. Hence, this language is not context-free.
• Option D: $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$ is the union of three context-free languages: $\{a^nb^n\} \cup \{a^nb^{3n}\} \cup \{a^nb^{5n}\}$. Since context-free languages are closed under union, this language is context-free.