Which of the following pairs have DIFFERENT expressive power?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2011 · Q8
MCQ1 markEasy
Time
Which of the following pairs have **DIFFERENT** expressive power?
Select one answerSingle correct
Pick an option to check
Solution
Step-by-step verified solution
Official answer: B) Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
Context-Free Grammars and PDAsLet's analyze the expressive power of each pair:
(A) DFA and NFA: Both accept exactly the class of regular languages. Thus, their expressive power is the same.
(B) DPDA and NPDA: Deterministic Pushdown Automata (DPDA) accept Deterministic Context-Free Languages (DCFLs), whereas Non-Deterministic Pushdown Automata (NPDA) accept all Context-Free Languages (CFLs). Since , they have different expressive power.
(C) Deterministic single-tape TM and Non-deterministic single-tape TM: Both recognize the same class of languages (Recursively Enumerable languages). Their expressive power is the same.
(D) Single-tape TM and Multi-tape TM: A multi-tape TM can be simulated by a single-tape TM; both have identical expressive power.
Therefore, option (B) is the correct choice.
Try the question first, then check your work.
Examiner trap
The misconception this question tests
Recall which class of automata is strictly less powerful in its deterministic variant compared to its non-deterministic counterpart.
This Context-Free Grammars and PDAs previous year question is Q8 of the GATE CSE 2011 paper. Find more GATE CSE PYQs on Context-Free Grammars and PDAs in Theory of Computation, or browse all GATE CSE PYQs.
Free diagnostic
Where do you stand for GATE?
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Context-Free Grammars and PDAs PYQs now with no account.
One GATE CSE PYQ every morning
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Context-Free Grammars and PDAs in GATE CSE
Context-Free Grammars and PDAs has 26 GATE CSE PYQs across 17 papers from 2011 to 2026. 9 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2011.
How GATE tests Context-Free Grammars and PDAsMore from GATE CSE 2011
- Q10Which one of the following is NOT desired in a good Software Requirement Specifications (SRS) document?MCQ1 markEasy
- Q6Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the followin…MCQ1 markEasy
- Q11A computer handles several interrupt sources of which the following are relevant for this question. • Interrupt from CPU temperature sensor (raises interrupt i…MCQ1 markEasy
- Q5A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of…MCQ1 markMedium
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.