Suppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily context-free?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2021 Set 1 · Q1
Time
Select one answerSingle correct
Solution
Official answer: C) L1 - L2
Context-Free Grammars and PDAsLet be a regular language and be a context-free language (CFL).
Intersection (): Context-free languages are closed under intersection with regular languages. The cross-product construction of a Pushdown Automaton (PDA) and a Deterministic Finite Automaton (DFA) yields a PDA. Thus, is always context-free.
Concatenation (): Since regular languages are also CFLs, this is the concatenation of two CFLs, which is always context-free.
Union (): CFLs are closed under union. Since is regular (and hence context-free) and is context-free, is always context-free.
Difference (): By set theory, . If were always context-free, then choosing (which is regular) would mean is always context-free. However, CFLs are not closed under complementation. Therefore, is not necessarily context-free.
Hence, the correct option is (C).
Try the question first, then check your work.
Examiner trap
Recall the closure properties of context-free languages. Express set difference in terms of intersection and complementation: . Are CFLs closed under complementation?
This Context-Free Grammars and PDAs previous year question is Q1 of the GATE CSE 2021 Set 1 paper. Find more GATE CSE PYQs on Context-Free Grammars and PDAs in Theory of Computation, or browse all GATE CSE PYQs.
Free diagnostic
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.
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 has 26 GATE CSE PYQs across 17 papers from 2011 to 2026. 9 of them are 1-mark MCQs like this one, and GATE CSE 2021 Set 1 has 2.
How GATE tests Context-Free Grammars and PDAsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.