The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
1.5k views

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

  1. The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.

  2. Non-deterministic Push-down automata are equivalent to deterministic Push-down automata.

  3. Non-deterministic Turing machines are equivalent to deterministic Push-down automata.

  4. Non-deterministic Turing machines are equivalent to deterministic Turing machines.

  5. Multi-tape Turing machines are available are equivalent to Single-tape Turing machines.

asked in Theory of Computation by Veteran (59.5k points) | 1.5k views

2 Answers

+17 votes
Best answer
  1. True. Proof - Subset Construction Procedure
  2. False. No conversion from NPDA To DPDA$>$
  3. False. Power(TM) $>$ NPDA $>$ DPDA.
  4. True
  5. True

Answer: This question has multiple answers, B and C.

answered by Boss (42.6k points)
edited by
0
C is false.Please check.NTM==DTM
–1 vote
Ans B
answered by Loyal (6.1k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,939 questions
45,453 answers
131,190 comments
48,204 users