Question

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

• A. Any regular language.
• B. Any context-free language.
• C. Any language accepted by a non-deterministic pushdown automaton.
• D. Any decidable language.

Hint:

Remember: DPDA accepts all regular languages but only some context-free languages (not all).

Answer 1

The Correct Option is A

Step 1: Understanding deterministic pushdown automaton (DPDA).
A deterministic pushdown automaton (DPDA) is a type of pushdown automaton in which, for every state, input symbol, and stack symbol, there is at most one possible transition. Unlike NPDA, it cannot make multiple choices.
Step 2: Languages accepted by DPDA.
DPDA can accept only a proper subset of context-free languages, called deterministic context-free languages (DCFLs). However, every regular language can always be accepted by a DPDA.
Step 3: Relationship with other language classes.
Regular languages ⊆ Deterministic CFLs ⊆ Context-Free Languages.
Step 4: Analyzing the options.
(A) Any regular language: Correct — every regular language can be accepted by a DPDA (a DPDA can simply ignore its stack).
(B) Any context-free language: Incorrect — some CFLs (e.g., \( \{ ww^R \} \)) require non-determinism and cannot be accepted by a DPDA.
(C) Any language accepted by an NPDA: Incorrect — NPDAs are strictly more powerful than DPDAs.
(D) Any decidable language: Incorrect — many decidable languages are not even context-free, so DPDA cannot accept them.
Step 5: Conclusion.
The correct answer is (A) Any regular language.