GATE CSE 1992 | Question: 02,xx

Question

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-deterministic Turing machine.
• D. For no machines $M_{1}$ and $M_2$,  the above statement true.

Answer 1

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.