Let Nf and Np denote the classes of languages accepted by non-deterministic…
2005
Let Nf and Np denote the classes of languages accepted by non-deterministic 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?
- A.
Df ⊂ Nf and Dp ⊂ Np
- B.
Df ⊂ Nf and Dp = Np
- C.
Df = Nf and Dp = Np
- D.
Df = Nf and Dp ⊂ Np
Attempted by 30 students.
Show answer & explanation
Correct answer: D
Deterministic finite automata (Df) and non-deterministic finite automata (Nf) recognize the same class of languages, so Df = Nf. However, deterministic push-down automata (Dp) are less powerful than non-deterministic push-down automata (Np), as there exist context-free languages that can be recognized by Np but not by Dp. Thus, Dp ⊂ Np.
A video solution is available for this question — log in and enroll to watch it.