3,416 views

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.

• 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.