Sort DFA, NFA, deterministic PDA, non-deterministic PDA, deterministic TM, non-d

Question

Sort DFA, NFA, deterministic PDA, non-deterministic PDA, deterministic TM, non-deterministic TM into an increasing order of computability power.
A. DFA, NFA, deterministic PDA, non-deterministic PDA, deterministic TM, non-deterministic TM
B. DFA and NFA tied, deterministic PDA, non-deterministic PDA, deterministic TM, non-deterministic TM
C. DFA, NFA, deterministic PDA and non-deterministic PDA tied, deterministic TM, non-deterministic TM
D. DFA and NFA tied, deterministic PDA, non-deterministic PDA, deterministic TM and non-deterministic TM tied.

Explanation / Answer

Here Answer is (D) DFA and NFA tied, deterministic PDA, non-deterministic PDA, deterministic TM, non-deterministic TM.

Explanation : As there exist algorithm to convert any NFA to its equvalent DFA, i.e DFA and NFA have same power .

Power of non- deterministic PDA is greater than Deterministic PDA and we cant convert NPDA to DPDA.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.