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

A
Single-tape-turing machine and multi-dimensional turing machine.
B
Multi-tape turing machine and multi-dimensional turing machine.
C
Deterministic pushdown automata and non-deterministic pushdown automata.
D
Deterministic finite automata and Non-deterministic finite automata
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!