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

- $M_{1}$ is non-deterministic finite automaton.
- $M_{1}$ is non-deterministic PDA.
- $M_{1}$ is a non-deterministic Turing machine.
- For no machines $M_{1}$ and $M_2$, the above statement true.

52,345 questions

60,497 answers

201,862 comments

95,319 users