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.