GateAI
Regular and Context-Free Languages

GATE CSE 2017 Set 2 · Q4

MCQ1 markMedium

Time

Let L1,L2L_1, L_2 be any two context-free languages and RR be any regular language. Then which of the following is/are CORRECT? I. L1∪L2L_1 \cup L_2 is context-free. II. L1‾\overline{L_1} is context-free. III. L1−RL_1 - R is context-free. IV. L1∩L2L_1 \cap L_2 is context-free.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) I and III only

Regular and Context-Free Languages

Let us examine the closure properties of Context-Free Languages (CFLs):

  1. Statement I is TRUE: Context-free languages are closed under union. If L1L_1 and L2L_2 are CFLs, L1∪L2L_1 \cup L_2 is context-free.

  2. Statement II is FALSE: Context-free languages are not closed under complementation. The complement L1‾\overline{L_1} is not necessarily context-free.

  3. Statement III is TRUE: CFLs are closed under set difference with regular languages. Since L1−R=L1∩R‾L_1 - R = L_1 \cap \overline{R}, and regular languages are closed under complementation, R‾\overline{R} is regular. The intersection of a CFL and a regular language is always a CFL, so L1−RL_1 - R is context-free.

  4. Statement IV is FALSE: Context-free languages are not closed under intersection. L1∩L2L_1 \cap L_2 is not necessarily context-free.

Thus, statements I and III only are correct, corresponding to option (B).

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 Regular and Context-Free Languages previous year question is Q4 of the GATE CSE 2017 Set 2 paper. Find more GATE CSE PYQs on Regular and Context-Free Languages 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 Regular and Context-Free Languages 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.

Regular and Context-Free Languages in GATE CSE

Regular and Context-Free Languages has 21 GATE CSE PYQs across 13 papers from 2011 to 2026. 5 of them are 1-mark MCQs like this one, and GATE CSE 2017 Set 2 has 2.

How GATE tests Regular and Context-Free Languages

More from GATE CSE 2017 Set 2

Share this solution

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

GateAI solution cardGATE CSE 2017 Set 2 · Q4 · MCQ

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L1 ∪ L2 is context-free. II. L1 is context-free. III. L1 - R is context-free. IV. L1 ∩ L2 is 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.