GateAI
Context-Free Grammars and PDAs

GATE CSE 2021 Set 1 · Q1

MCQ1 markMedium

Time

Suppose that L1L_1 is a regular language and L2L_2 is a context-free language. Which one of the following languages is NOT necessarily context-free?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) L1 - L2

Context-Free Grammars and PDAs

Let L1L_1 be a regular language and L2L_2 be a context-free language (CFL).

  1. Intersection (L1∩L2L_1 \cap L_2): 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, L1∩L2L_1 \cap L_2 is always context-free.

  2. Concatenation (L1⋅L2L_1 \cdot L_2): Since regular languages are also CFLs, this is the concatenation of two CFLs, which is always context-free.

  3. Union (L1∪L2L_1 \cup L_2): CFLs are closed under union. Since L1L_1 is regular (and hence context-free) and L2L_2 is context-free, L1∪L2L_1 \cup L_2 is always context-free.

  4. Difference (L1−L2L_1 - L_2): By set theory, L1−L2=L1∩L2‾L_1 - L_2 = L_1 \cap \overline{L_2}. If L1−L2L_1 - L_2 were always context-free, then choosing L1=Σ∗L_1 = \Sigma^* (which is regular) would mean Σ∗−L2=L2‾\Sigma^* - L_2 = \overline{L_2} is always context-free. However, CFLs are not closed under complementation. Therefore, L1−L2L_1 - L_2 is not necessarily context-free.

Hence, the correct option is (C).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

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 GATE CSE 2021 Set 1 has 2.

How GATE tests Context-Free Grammars and PDAs

More from GATE CSE 2021 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 1 · Q1 · MCQ

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

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.