Question 41

Let us examine the languages:

• Option A: $\{ww^R \mid w \in \{a, b\}^*\}$ is the standard even palindrome language, which is generated by $S \to aSa \mid bSb \mid \epsilon$ and accepted by an NPDA. (Context-free)
• Option B: $\{w a^n b^n w^R\}$ is generated by $S \to aSa \mid bSb \mid A$ where $A \to aAb \mid \epsilon$. The PDA pushes $w$, then matches $a^n b^n$, and finally matches $w^R$ against the remaining stack. (Context-free)
• Option C: $\{w a^n w^R b^n\}$. In any string of this language, the palindrome matching of $w$ with $w^R$ is interleaved with the count matching of $a^n$ with $b^n$. A single stack cannot verify that $w^R$ matches $w$ while simultaneously preserving the count $n$ of $a$'s to match against $b^n$ appearing later. By the Pumping Lemma for CFLs, choosing $s = a^p b^p a^p b^p a^p$ shows that this language is NOT context-free.
• Option D: $\{a^n b^i \mid i \in \{n, 3n, 5n\}\} = \{a^n b^n\} \cup \{a^n b^{3n}\} \cup \{a^n b^{5n}\}$. Each of these three languages is context-free, and context-free languages are closed under finite union. (Context-free)