GATE 2017 CS (CS2) – Question 50

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

L₁={aᵖ:p prime}, $L_2=\{a^nb^mc^{2m}:n,m\ge0\}$, $L_3=\{a^nb^nc^{2n}:n\ge0\}$, L₄={aⁿbⁿ:n≥1}. Which hold? I: L₁ context-free but not regular. II: L₂ not context-free. III: L₃ not context-free but recursive. IV: L₄ deterministic context-free.

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) III and IV only

Explanation

Every unary context-free language is regular, whereas prime-length unary strings are nonregular, so I is false. L₂ is context-free: ignore the a-prefix and match one b to two c’s, so II is false. L₃ is decidable by counting but is non-CFL via inverse homomorphism to aⁿbⁿcⁿ, proving III. A deterministic PDA matches L₄’s a’s to b’s, proving IV. Thus D.

More Regular and Context-Free Languages, Pumping Lemma questions

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\+ \…
GATE 2025 CS (CS1) Q45 – Consider the following two languages over the alphabet \a,b,c\, where m and n are natural…

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