GATE CS 2025 Set 2 | Question 24

MCQ · 1 mark · −0.33

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

  1. Option A: Any regular language. (correct)
  2. Option B: Any context-free language.
  3. Option C: Any language accepted by a non-deterministic pushdown automaton.
  4. Option D: Any decidable language.

Answer

(A)

Explanation

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