Correct : a
The correct answer is Option A - Any regular language.
A Deterministic Pushdown Automaton (DPDA) accepts the class of languages known as Deterministic Context-Free Languages (DCFLs). Since regular languages are a strict subset of DCFLs, every regular language is accepted by some DPDA. The DPDA simply simulates a DFA by ignoring the stack entirely.
Let''s check the other options:
Option B - Any context-free language: False. Not all CFLs are deterministic. Classic examples like the language of even-length palindromes {wwR} require non-determinism and cannot be accepted by any DPDA.
Option C - Any language accepted by NPDA: False. NPDAs accept all CFLs, but DPDAs accept only DCFLs — a proper subset. DPDA ⊂ NPDA in power.
Option D - Any decidable language: False. Decidable languages include everything recursive (Turing-decidable), which is far beyond what a pushdown automaton - deterministic or not - can handle.
The hierarchy to remember: Regular ⊂ DCFL ⊂ CFL ⊂ Recursive ⊂ Recursively Enumerable. DPDAs sit exactly at the DCFL level.
Similar Questions
Total Unique Visitors