GATE CSE 2005 | Question: 54

Question

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?

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

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

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

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

Answer 1

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.

Answer 2

Ans: D

Expressive power of DFA and NFA are same but not true in case of DPDA and NPDA