UTpaper

Free mock tests & test series

Question 74Asked in UGC NET Computer Science, June 2017 (Paper II & III, Selected Questions)

Which of the following pairs have different expressive power?

  1. ASingle-tape-turing machine and multi-dimensional turing machine
  2. BMulti-tape turing machine and multi-dimensional turing machine
  3. CDeterministic push down automata and non-deterministic pushdown automata.
  4. DDeterministic finite automata and Non-deterministic finite automata
Show answerHide answer

Correct answer: (C) Deterministic push down automata and non-deterministic pushdown automata.

Explanation

Deterministic and non-deterministic pushdown automata have different expressive power (NPDA accept all context-free languages, DPDA only deterministic CFLs). DFA and NFA are equivalent, and all the Turing machine variants are equivalent.

From UGC NET Computer Science PYQ, June 2017 (Paper II & III, Selected Questions)

This is question 74 of UGC NET Computer Science PYQ, June 2017 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.