###### Question 6968 – Artificial-Intelligence

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

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

Which of the following pairs have different expressive power?

Correct Answer: C

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

Subscribe

Login

0 Comments