The Gateway to Computer Science Excellence
+20 votes

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

1 Answer

+23 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

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
52,345 questions
60,497 answers
95,319 users