Let Nf and Np denote the classes of languages accepted by

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic pushdown 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 ⊂ N_f and D_p ⊂ N_p
2. D_f ⊂ N_f and D_p = N_p
3. D_f = N_f and D_p = N_p
4. D_f = N_f and D_p ⊂ N_p

Correct Option: D

We know that, the languages accepted by non deterministic finite automata are also accepted by deterministic finite automata. This may not be in the case of context-free languages.
Therefore, D_f = N_f and D_p ⊂ N_p