in Theory of Computation edited by
24 votes

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-deterministic Turing machine.
  4. For no machines $M_{1}$ and $M_2$,  the above statement true.
in Theory of Computation edited by

1 Answer

29 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.
edited by

Related questions