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?

  1. A.

    The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.

  2. B.

    Non-deterministic Push-down automata are equivalent to deterministic Push-down automata.

  3. C.

    Non-deterministic Turing machines are not equivalent to deterministic Push-down automata.

  4. D.

    Non-deterministic Turing machines are equivalent to deterministic Turing machines.

  5. 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 free

Explore the full course: Zero To Hero

Loading lesson…