381 views

Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE?

1. $D_f \subset N_f \text{ and } D_p \subset N_p$

2. $D_f \subset N_f \text{ and } D_p = N_p$

3. $D_f = N_f \text{ and } D_p = N_p$

4. $D_f =N_f \text{ and } D_p \subset N_p$

asked | 381 views

Option D.

NFA and DFA both have equivalent power.(every nfa can be converted into equivalent dfa)  but NPDA can accept more languages than DPDA.
answered by Loyal (3.4k points)
selected
Ans: D

Expressive power of DFA and NFA are same but not true in case of DPDA and NPDA
answered by Boss (7.8k points)