GATE CS 2025 Set 2 | Question 24
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
Explanation
Answer: (A)
A DFA is simply a DPDA that never touches its stack, so every regular language is accepted by some DPDA. That makes (A) true.
- (B) and (C) describe the same class, because non-deterministic PDAs accept exactly the context-free languages. Both fail because DPDAs are strictly weaker: the even-length palindromes \(\{ww^{R} \mid w \in \{a, b\}^{*}\}\) are context-free, but no DPDA can tell where the middle of the input is.
- (D) fails because a decidable language such as \(\{a^{n}b^{n}c^{n} \mid n \ge 0\}\) is not even context-free, so no pushdown automaton of either kind accepts it.
Answer: A