The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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".      

(a). $M_{1}$ is non-deterministic finite automaton.

(b). $M_{1}$ is non-deterministic PDA.

(c). $M_{1}$ is a non-deteministic Turing machine.

(d). For no machines $M_{1}$ and $M_2$,  the above statement true.
asked in Theory of Computation by Veteran (68.9k points) | 468 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 Veteran (35.9k points)
selected 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

32,693 questions
39,293 answers
36,701 users