GATE 2011 CS (CS1) – Question 34

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

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 regular?

$P\cap Q$
$P-Q$
$\Sigma^*-P$
$\Sigma^*-Q$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Sigma^*-P$

Explanation

Regular languages are closed under complement, so Σ*−P is always regular, C. P∩Q equals Q under the subset premise and can be nonregular. Removing a nonregular CFL from P, or complementing that CFL, does not guarantee regularity.

More Regular and Context-Free Languages, Pumping Lemma questions

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?
GATE 2025 CS (CS2) Q30 – Consider the two lists List I and List II given below: List I List II --- --- (i) Context…

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