Theory-of-Computation
December 6, 2023GATE 1998
December 6, 2023GATE 1998
| Question 11 |
Regarding the power of recognition of languages, which of the following statements is false?
| The non-deterministic finite-state automata are equivalent to deterministic finite-state automata. | |
| Non-deterministic Push-down automata are equivalent to deterministic Push- down automata. | |
| Non-deterministic Turing machines are equivalent to deterministic Push-down automata. | |
| Both B and C |
Question 11 Explanation:
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
C: Power (TM) > NPDA > DPDA.
Correct Answer: D
Question 11 Explanation:
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
C: Power (TM) > NPDA > DPDA.