4,231 views
27 votes
27 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?

  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$

2 Answers

Best answer
29 votes
29 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.

edited by
Answer:

Related questions

19 votes
19 votes
3 answers
1
28 votes
28 votes
1 answer
4