Computer Sciences > GATE 2025 SET-2 > Pushdown Automata
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.

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

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From...
#1 MCQ
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
#4 MCQ
Choose the word that is opposite in meaning to the word “coherent”.
#5 MCQ

Related Topics

DPDA accepted language GATE 2025 GATE CS 2025 Set-2 Q24 deterministic pushdown automaton DPDA regular language DCFL deterministic CFL DPDA vs NPDA pushdown automaton GATE theory of computation GATE GATE computer science automata 2025

Unique Visitor Count

Total Unique Visitors

Loading......