L₁ is regular, L₂ context-free, L₃ recursive and L₄ recursively enumerable. Which hold? I: L 3 L 4 is recursively enumerable. II: L 2 L 3 is recursive. III: L 1* L 2 is context-free. IV: L 1L 2 is context-free.

GATE 2016 CS (CS2) – Question 28

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

L₁ is regular, L₂ context-free, L₃ recursive and L₄ recursively enumerable. Which hold? I: $\overline{L_3}\cup L_4$ is recursively enumerable. II: $\overline{L_2}\cup L_3$ is recursive. III: $L_1^*\cap L_2$ is context-free. IV: $L_1\cup\overline{L_2}$ is context-free.

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) I, II and III only

Explanation

Recursive languages are complement-closed, so the complement of L₃ is recursive and its union with the RE language L₄ is RE: I holds. Context-free languages are decidable, making the complement of L₂ recursive; its union with L₃ is recursive, so II holds. L₁* is regular and intersecting a CFL with a regular language preserves context-freeness, so III holds. IV need not hold because CFLs are not complement-closed; choosing L₁ empty supplies a counterexample. Therefore D.

More Regular and Context-Free Languages, Pumping Lemma questions

GATE 2016 CS (CS2) Q53 – L 1=\anbmcn+m:m,n1\ and L 2=\anbnc2n:n1\. Which holds?
GATE 2017 CS (CS2) Q14 – L₁,L₂ are context-free and R is regular. Which are correct? I: L₁∪L₂ is context-free. II:…
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?

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