GATE CS 1997 Q6.6 — Context-free Grammars and Push-down Automata

A language is accepted by a Deterministic Pushdown Automaton (DPDA) if and only if it is a Deterministic Context-Free Language (DCFL).

• Option A: $\{ wcw^R \mid w \in \{a,b\}^*\}$
  The symbol $c$ acts as a clear, unique marker separating $w$ and $w^R$. The DPDA can push symbols of $w$ onto the stack, and upon reading $c$, deterministically switch to popping and matching the remaining input against the stack. Thus, it is a DCFL and accepted by a DPDA.
• Option B: $\{ ww^R \mid w \in \{a,b,c\}^*\}$
  There is no middle marker. A PDA must non-deterministically guess the midpoint where $w$ ends and $w^R$ begins. Hence, it is not a DCFL.
• Option C: $\{ a^nb^nc^n \mid n \geq 0 \}$
  This is a well-known non-context-free language (CSL) and cannot be accepted by any PDA.
• Option D: Palindromes over $\{a,b,c\}$
  This includes even-length palindromes ($ww^R$) and odd-length palindromes ($waw^R, wbw^R, wcw^R$). Without a designated marker to identify the exact midpoint, it requires non-deterministic guessing and is not a DCFL.