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

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.4k points)
edited by | 553 views

1 Answer

+14 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 (34.2k points)
edited by

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

34,780 questions
41,755 answers
41,399 users