The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
749 views

02. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

In which of the cases stated below is the following statement true?

       "For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language".      

  1. $M_{1}$ is non-deterministic finite automaton.
  2. $M_{1}$ is non-deterministic PDA.
  3. $M_{1}$ is a non-deteministic Turing machine.
  4. For no machines $M_{1}$ and $M_2$,  the above statement true.
asked in Theory of Computation by Veteran (59.6k points)
edited by | 749 views

1 Answer

+16 votes
Best answer

Answer: A and C.

  • For every NFA there exists a DFA.
  • For every NPDA there does not exist a deterministic PDA.
  • Every nondeterministic Turing machine has an equivalent deterministic Turing Machine.
answered by Boss (34k points)
edited by

Related questions



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

42,658 questions
48,639 answers
156,232 comments
63,953 users