NFA
Question 1 |
Regarding the power of recognition of languages, which of the following statements is false?
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata. | |
Non-deterministic Push-down automata are equivalent to deterministic Push- down automata. | |
Non-deterministic Turing machines are equivalent to deterministic Push-down automata. | |
Both B and C |
Question 1 Explanation:
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
C: Power (TM) > NPDA > DPDA.
Question 2 |
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?
Df ⊂ Nf and Dp ⊂ Np
| |
Df ⊂ Nf and Dp = Np | |
Df = Nf and Dp = Np | |
Df = Nf and Dp ⊂ Np |
Question 2 Explanation:
NFA and DFA have equivalent powers.
So Df = Nf
NPDA can accept more languages than DPDA.
Dp ⊂ Np
So Df = Nf
NPDA can accept more languages than DPDA.
Dp ⊂ Np