Question 6968 – Artificial-Intelligence
March 1, 2024Question 6927 – Theory-of-Computation
March 1, 2024Question 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