PyQdeck LogoPyQdeckSubjectsSyllabusBlog
Back to the 2023 paper

Module 4: Turing Machines (TM)

20232m

From the options, the pair having different expressive powers is:

(i) DPDA and NPDA
(ii) DFA and NFA
(iii) single-tape TM and multi-tape TM
(iv) deterministic single-tape TM and nondeterministic single-tape TM

Search GoogleAsk AI
Worked SolutionAI Assisted

Answer

Correct Option: (i) DPDA and NPDA

Explanation

Expressive power comparison:

Pair Power Same?
DPDA vs NPDA Different — NPDA = CFL, DPDA = DCFL ⊂ CFL. Example {anbn}∪{anb2n}\{a^n b^n\}\cup\{a^n b^{2n}\} is CFL but not DCFL.
DFA vs NFA Same — both = Regular
Single-tape TM vs Multi-tape TM Same — both = RE, polytime difference only
Deterministic single-tape TM vs Nondeterministic single-tape TM Same — DTM=NTMDTM = NTM in power

Hence different expressive powers is DPDA vs NPDA.

Final Answer

DPDA and NPDA have different power → Option (i).

Similar questions

Formal Language & Automata TheoryWhich of the following pairs have DIFFERENT expressive powers? (i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA) (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA) (iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine (iv) Single-tape Turing machine and multi-tape Turing machine20222m Compiler DesignWhich automaton accepts regular languages? (i) PDA (ii) DFA (iii) Turing machine (iv) LBA20252mFormal Language & Automata TheoryEpsilon (\varepsilon) transitions are allowed in (i) DFA only (ii) Both DFA and NFA (iii) NFA only (iv) None20252mFORMAL LANGUAGE & AUTOMATA THEORYA DFA can have: (i) Multiple start states (ii) Multiple accepting states (iii) Transitions on \varepsilon (iv) None of the above20242m
PreviousWhich one of the following statements is true? (i) The intersection of two CFLs is context-free (ii) Every CFL can be accepted by a DPDA (iii) The union of two CFLs is context-free (iv) The complement of a CFL is context-freeNextRecursive languages are: (i) a proper superset of CFLs (ii) always recognizable (iii) also called type-0 languages (iv) recognizable by Turing machines
AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.

Try Coursify Free