Question:medium

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

Show Hint

Remember: DPDA accepts all regular languages but only some context-free languages (not all).
Updated On: Feb 9, 2026
  • Any regular language.
  • Any context-free language.
  • Any language accepted by a non-deterministic pushdown automaton.
  • Any decidable language.
Show Solution

The Correct Option is A

Solution and Explanation

Step 1: Recall what a deterministic pushdown automaton is. 
A deterministic pushdown automaton (DPDA) is a pushdown automaton in which the next move is uniquely determined.
For any given state, input symbol, and top stack symbol, there is at most one valid transition.
Unlike a nondeterministic PDA, a DPDA cannot branch into multiple computational paths.

Step 2: Identify the class of languages recognized by DPDAs.
DPDAs recognize a special subclass of context-free languages known as deterministic context-free languages (DCFLs).
Although this class is smaller than the class of all context-free languages, it still includes all regular languages.

Step 3: Understand the hierarchy of language classes.
The inclusion relationship among these classes is:

\[ \text{Regular Languages} \subseteq \text{Deterministic CFLs} \subseteq \text{Context-Free Languages} \]

Step 4: Evaluate the given options.
(A) Any regular language: This is correct. A DPDA can simulate a finite automaton and may even ignore its stack entirely.
(B) Any context-free language: This is incorrect, since some CFLs require nondeterminism and cannot be handled by a DPDA.
(C) Any language accepted by an NPDA: Incorrect, because nondeterministic PDAs are strictly more powerful than deterministic ones.
(D) Any decidable language: Incorrect, as many decidable languages lie outside the context-free family.

Step 5: Final conclusion.
A deterministic pushdown automaton can accept:

\[ \boxed{\text{Any regular language}} \]

Was this answer helpful?
0