L 1=\0p1q0r:p,q,r0\ and L 2=\0p1q0r:p,q,r0,p r\. Which statement is false?

The complement of L₂ is recursive

GATE 2013 CS (CS1) – Question 42

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 2 marks · Multiple choice

$L_1=\{0^p1^q0^r:p,q,r\ge0\}$ and $L_2=\{0^p1^q0^r:p,q,r\ge0,p\ne r\}$. Which statement is false?

L₂ is context-free
L₁∩L₂ is context-free
The complement of L₂ is recursive
The complement of L₁ is context-free but not regular

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) The complement of L₁ is context-free but not regular

Explanation

L₁=0*1*0* is regular, so its complement is also regular. Thus D’s claim “not regular” is false. L₂ is a union of the p<r and p>r languages, each handled by stack comparison, so it is context-free. L₂⊆L₁ makes their intersection L₂; its complement is decidable by block checking and counting.

More Regular and Context-Free Languages, Pumping Lemma questions

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\+ \…
GATE 2025 CS (CS1) Q45 – Consider the following two languages over the alphabet \a,b,c\, where m and n are natural…
GATE 2025 CS (CS2) Q24 – Which ONE of the following languages is accepted by a deterministic pushdown automaton?

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