GATE CS 2025 Set 2 Q14 — Context-free Grammars and Push-down Automata

To determine which class of languages is accepted by a Deterministic Pushdown Automaton (DPDA), let us analyze the language hierarchies and the capabilities of a DPDA:

• Deterministic Context-Free Languages (DCFLs): This is the exact class of languages accepted by DPDAs.
• Regular Languages: Every regular language can be recognized by a Deterministic Finite Automaton (DFA). Since a DFA is simply a DPDA that does not use its stack, every regular language is also a DCFL. Mathematically, $\text{Regular} \subset \text{DCFL}$. Therefore, any regular language is accepted by a DPDA.
• Context-Free Languages (CFLs) / Languages accepted by an NPDA: There exist context-free languages (such as the language of even palindromes, $L = \{ww^R \mid w \in \{a, b\}^*\}$) that are inherently non-deterministic and cannot be accepted by any DPDA. Thus, options B and C are incorrect.
• Decidable Languages: This class includes languages like $L = \{a^n b^n c^n \mid n \ge 0\}$ which are not context-free and require a Turing Machine to be decided. They cannot be accepted by a DPDA. Thus, option D is incorrect.

Hence, the correct option is A.