NFA

Question 1

Regarding  the power of recognition of languages, which of the following statements is false?

A
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
B
Non-deterministic Push-down automata are equivalent to deterministic Push- down automata.
C
Non-deterministic Turing machines are equivalent to deterministic Push-down automata.
D
Both B and C
Question 1 Explanation: 
B: No conversion possible from NPDA to 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?

A
Df ⊂ Nf and Dp ⊂ Np
B
Df ⊂ Nf and Dp = Np
C
Df = Nf and Dp = Np
D
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
There are 2 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access