March 1, 2024
March 1, 2024
March 1, 2024
###### Question 6927 – Theory-of-Computation
March 1, 2024

Which of the following pairs have different expressive power?

Question 504 Explanation:
Option(A): It is incorrect option because using multi-dimensional turing machine we can speed up the process of accepting the language but it does not mean that Single-tape-turing machine can’t accept the string that multidimensional turing machine accepts.

Option(B): is also incorrect because both machines are same so they can accept the same string with same speed.

Option(C) : It is correct option because Non deterministic pushdown automata is more powerful than deterministic pushdown automata because by using non-deterministic pushdown automata L= {ww | w belongs to (a,b)*} can be accepted but the same language can’t be accepted using deterministic pushdown automata.

Option(D) : it is incorrect option because DFA and NDFA both are equivalent to each other i.e. we can convert DFA into NFA and NFA into DFA. DFA and NFA are equal in powers and can accept the same strings.

Single-tape-turing machine and multi-dimensional turing machine.
Multi-tape turing machine and multi-dimensional turing machine.
Deterministic pushdown automata and non-deterministic pushdown automata.
Deterministic finite automata and Non-deterministic finite automata