• retagged by
6,686 views
15 15 votes

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

  1. Any regular language
  2. Any context-free language
  3. Any language accepted by a non-deterministic pushdown automaton
  4. Any decidable language
 

4 Answers

17 17 votes
Since regular languages are a subset of deterministic context-free languages (DCFL), every regular language is also a DCFL.

Context-free languages (CFL) and recursive (decidable) languages are supersets of DCFL.

 Thus, option $(A)$ is correct.

 
1 1 vote

DPDA accepts deterministic context free languages (DCFLs). Regular languages are subset of DCFLs, hence a DPDA accepts any regular language. 

Option B and D are supersets of DCFLs hence they are incorrect. 

NPDA is more powerful than DPDA hence it can accept languages that DPDA cannot accept. Hence option C is incorrect.

Hence answer is option A.

1 1 vote

Option A: Any regular language

Every regular language is accepted by a deterministic finite automaton (DFA). A DFA can be viewed as a DPDA that never uses its stack (or uses it trivially). Hence, every regular language is a deterministic context-free language (DCFL) and is accepted by a DPDA.

 

Option B: Any context-free language

Not all context-free languages are deterministic. A classic counterexample is  
$$
L = \{ w w^R \mid w \in \{a,b\}^* \},
$$  
the set of even-length palindromes. Any DPDA would need to know the exact middle of the input to switch from pushing to popping, but without a marker, it cannot do so deterministically. Thus, $ L \in \text{CFL} \setminus \text{DCFL} $.  Not accepted by any DPDA.

 

Option C: Any language accepted by a non-deterministic PDA

Languages accepted by NPDAs are exactly the CFLs. As shown above, some CFLs are not DCFLs. Hence, this class strictly contains languages not accepted by any DPDA.  
Incorrect.

Option D: Any decidable language

Decidable languages include languages that are not even context-free. For example,  
$$
L = \{ a^n b^n c^n \mid n \geq 0 \}
$$  
is decidable (a Turing machine can count and compare), but it is not context-free, so no PDA deterministic or not can accept it. Since DPDAs accept only DCFLs ⊂ CFL ⊂ Decidable, this is false.  
Not accepted by a DPDA.

Only regular languages are guaranteed to be accepted by a DPDA among the given options.

$$
\color{skyblue} \boxed{\text{Answer: A}}
$$

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
1.6k
1.6k views
eggs asked Feb 27, 2025
1,559 views
Which ONE of the following languages is accepted by a deterministic pushdown automaton?Any regular language.Any context-free language.Any language accepted by a non-deter...
16 16 votes
4 4 answers
7.2k
7.2k views
Arjun asked Feb 27, 2025
7,203 views
​​​​Let $G_{1}, G_{2}$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$.Which ONE among...
17 17 votes
7 7 answers
6.9k
6.9k views
Arjun asked Feb 27, 2025
6,891 views
Consider the two lists List I and List II given below:\[\begin{array}{|l|l|}\hline \textbf{List I} & \textbf{List II} \\\hline \text{Context-free languages} & \text{Close...
22 22 votes
11 11 answers
13.5k
13.5k views
admin asked Feb 27, 2025
13,494 views
Consider two grammars $G_{1}$ and $G_{2}$ with the production rules given below: $G_{1} : S \rightarrow$ $if$ $E$ $then$ $S$ $|$ $if$ $E$ $then$ $S$ $else$ $S$ $|$ $a$ ...