32 32 votes 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? $D_f \subset N_f \text{ and } D_p \subset N_p$ $D_f \subset N_f \text{ and } D_p = N_p$ $D_f = N_f \text{ and } D_p = N_p$ $D_f =N_f \text{ and } D_p \subset N_p$ Theory of Computation gatecse-2005 theory-of-computation easy non-determinism + – Kathleen 6.8k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 34 34 votes Correct 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. shree answered Dec 26, 2014 • edited May 6, 2021 by soujanyareddy13 shree comment Share Follow See 1 comment 1 1 comment reply quack_quack commented Jul 12 reply Follow flag NPDA can accept more languages than DPDA because of null moves right? 0 0 replyShare Please log in or register to add a comment.
4 4 votes Ans: D Expressive power of DFA and NFA are same but not true in case of DPDA and NPDA rishu_darkshadow answered Nov 15, 2017 rishu_darkshadow comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes DFA = NFA < DPDA < NPDA < LBA < DTM = NTM Pranay_VG answered Dec 31, 2025 Pranay_VG comment Share Follow 0 reply Please log in or register to add a comment.
