Multiple choice

Let Nf and Np denote the classes of languages accepted by nondeterministic finite automata and non-deterministic push-down automata, respectively. let Df and DP denote the classes of languages accepted by deterministic finite automata and deterministic push down automata, respectively. Which one of the following is true?

  1. Df $\subset$ Nf and DP $\subset$ NP
  2. Df $\subset$ Nf and DP = NP

  3. Df = Nf and DP = NP
  4. Df = Nf and DP $\subset$ NP
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Keep practicing — related questions