The GATE Grind

GATE 2025 CS (CS2) – Question 24

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

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

  1. Any regular language.
  2. Any context-free language.
  3. Any language accepted by a non-deterministic pushdown automaton.
  4. Any decidable language.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Any regular language.

Explanation

Every regular language is a DCFL, so a DPDA accepts it. DPDAs are strictly weaker than NPDAs (e.g., even palindromes), and decidable languages go beyond CFLs.