Computer Sciences > GATE 2025 SET-2 > Pushdown Automata
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
Correct : a
Correct Answer:
a) Any regular language.
A deterministic pushdown automaton (DPDA) can accept all regular languages, because it can simulate any deterministic finite automaton (DFA), which recognizes regular languages.
Regular languages are a strict subset of deterministic context-free languages, but not all context-free languages are accepted by a DPDA—some require non-determinism.
The languages accepted by a DPDA (called deterministic context-free languages, DCFLs) include all regular languages, but not all context-free, NPDA-accepted, or decidable languages.
Total Unique Visitors
Loading......