Which ONE of the following languages is accepted by a deterministic pushdown automaton?
Correct Answer :
Any regular language.
Solution :
The correct option is Any regular language.
To understand why this is correct, we can analyze the relationships between different classes of automata and the languages they accept.
A Deterministic Pushdown Automaton (DPDA) is a computational model that is similar to a Deterministic Finite Automaton (DFA) but has the added capability of using a single stack memory. The class of languages accepted by DPDAs is known as the Deterministic Context-Free Languages (DCFLs).
Any regular language can be recognized by a standard DFA. Since a DFA is simply a DPDA that does not make use of its stack (or leaves the stack stack-pointer unchanged), any language that can be accepted by a DFA can also be accepted by a DPDA. Thus, the set of regular languages is a strict subset of the set of deterministic context-free languages. Therefore, any regular language is accepted by a deterministic pushdown automaton.
Let's examine why the other options are incorrect:
- Any context-free language: The class of Context-Free Languages (CFLs) is larger than the class of DCFLs. Some context-free languages are inherently non-deterministic and cannot be accepted by any deterministic PDA (for example, the language of even palindromes).
- Any language accepted by a non-deterministic pushdown automaton: A non-deterministic pushdown automaton (NPDA) accepts the entire class of Context-Free Languages. Because DPDAs cannot accept all CFLs, they cannot accept every language that an NPDA can accept.
- Any decidable language: Decidable languages include languages that are not context-free, such as:
These require more powerful machines, like Turing machines, and cannot be accepted by a DPDA.
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Mindyard. Perfect for teachers and institutes.
Copyright © 2026 Mindyard. All Rights Reserved.