GATE 2011 CS (CS1) – Question 18

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

Which pair has different expressive power?

DFA and NFA
Deterministic PDA and nondeterministic PDA
Deterministic single-tape TM and nondeterministic single-tape TM
Single-tape TM and multitape TM

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Deterministic PDA and nondeterministic PDA

Explanation

DFAs and NFAs recognize the same regular languages. Deterministic and nondeterministic TMs, including multitape variants, have equal language-recognition power. Deterministic PDAs recognize only a proper subset of context-free languages, unlike NPDAs. Thus B.

More Turing Machines and Undecidability questions

GATE 2010 CS (CS1) Q27 – L₁ is recursive. L₂,L₃ are recursively enumerable but nonrecursive. Which is NOT…
GATE 2015 CS (CS2) Q20 – Which statements are true? I: The complement of every Turing-decidable language is…
GATE 2021 CS (CS2) Q46 – S1: Every infinite regular language has an undecidable language as a subset. S2: Every…
GATE 2026 CS (CS2) Q13 – Which one of the following statements is equivalent to the assertion: Turing machine M…
GATE 2025 CS (CS2) Q25 – Let G 1, G 2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar…
GATE 2022 CS Q46 – Which of the following is/are undecidable?

All Turing Machines and Undecidability questions →