The GATE Grind

GATE 2011 CS (CS1) – Question 36

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

$L_1=\{0^p1^q:p,q\in\mathbb N\}$, $L_2=\{0^p1^q:p,q\in\mathbb N,p=q\}$, $L_3=\{0^p1^q0^r:p,q,r\in\mathbb N,p=q=r\}$. Which is NOT true?

  1. A PDA can recognize L₁ and L₂
  2. L₁ is regular
  3. All three are context-free
  4. A TM can recognize all three

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) All three are context-free

Explanation

L₁ is a regular two-block language and L₂ is matched aⁿbⁿ form, recognized by a PDA. L₃ requires three equal-sized blocks and is not context-free, by the standard pumping argument for three-way equality. All are decidable by counting, hence TM-recognizable. Thus C is false.

More Regular and Context-Free Languages, Pumping Lemma questions

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