Solved Paper-II On Topic : Solved Paper-II June 2005

Que : 1 . Which of the following is not true?

1. Power of deterministic automata is equivalent to power of non-deterministic automata.
2. Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.
3. Power of deterministic Turing machine is equivalent to power of non-deterministic Turing machine.
4. All the above
Please Select Ans Options .
Explanation

Option 2 is Correct Answer.
Deterministics and non-deterministic finite automata have equivalent computational capabilities.
Deterministic and non-deterministic Turing machines have the same computational capabilities.
However, the computational capabilities of deterministics push-down automata are less than those of non-deterministic push-down automata.