Regarding the power of recognition of languages, which of the following…
PYQ GATE 1998Modified — slightly modified from the official paper; see the solution
Regarding the power of recognition of languages, which of the following statements is false?
- A.
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
- B.
Non-deterministic Push-down automata are equivalent to deterministic Push-down automata.
- C.
Non-deterministic Turing machines are not equivalent to deterministic Push-down automata.
- D.
Non-deterministic Turing machines are equivalent to deterministic Turing machines.
- E.
Multi-tape Turing machines are equivalent to Single-tape Turing machines.
Attempted by 307 students.
Sign up free to check your answer
Sign up freeLoading lesson…

