L₁,L₂ are context-free and R is regular. Which are correct? I: L₁∪L₂ is context-free. II: L 1 is context-free. III: L₁−R is context-free. IV: L₁∩L₂ is context-free.

GATE 2017 CS (CS2) – Question 14

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

L₁,L₂ are context-free and R is regular. Which are correct? I: L₁∪L₂ is context-free. II: $\overline{L_1}$ is context-free. III: L₁−R is context-free. IV: L₁∩L₂ is context-free.

I, II and IV only
I and III only
II and IV only
I only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) I and III only

Explanation

CFLs are closed under union, proving I. Also $L_1-R=L_1\cap\overline R$; regular languages are complement-closed and intersecting a CFL with a regular language preserves context-freeness, proving III. CFLs are not generally closed under complement or intersection, so II and IV fail. Thus B.

More Regular and Context-Free Languages, Pumping Lemma questions

GATE 2017 CS (CS2) Q50 – L₁=aᵖ:p prime, L 2=\anbmc2m:n,m0\, L 3=\anbnc2n:n0\, L₄=aⁿbⁿ:n≥1. Which hold? I: L₁…
GATE 2013 CS (CS1) Q42 – L 1=\0p1q0r:p,q,r0\ and L 2=\0p1q0r:p,q,r0,p r\. Which statement is false?
GATE 2011 CS (CS1) Q34 – P is regular and Q is context-free with Q⊆P, e.g. P=p*q* and Q=pⁿqⁿ:n∈N. Which is always…
GATE 2011 CS (CS1) Q36 – L 1=\0p1q:p,q N\, L 2=\0p1q:p,q N,p=q\, L 3=\0p1q0r:p,q,r N,p=q=r\. Which is NOT true?
GATE 2015 CS (CS2) Q46 – Which languages are regular? L 1=\wxwR:w,x\a,b\*,\ w , x >0\; L 2=\anbm:m n,\ m,n0\; L…
GATE 2025 CS (CS1) Q44 – Consider the following two languages over the alphabet \a,b\: L 1 = \ \a,b\+ AND \a,b\+ \…

All Regular and Context-Free Languages, Pumping Lemma questions →