The GATE Grind

GATE 2015 CS (CS2) – Question 46

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

Which languages are regular? $L_1=\{wxw^R:w,x\in\{a,b\}^*,\ |w|,|x|>0\}$; $L_2=\{a^nb^m:m\ne n,\ m,n\ge0\}$; $L_3=\{a^pb^qc^r:p,q,r\ge0\}$.

  1. L₁ and L₃ only
  2. L₂ only
  3. L₂ and L₃ only
  4. L₃ only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) L₁ and L₃ only

Explanation

For L₁, any valid word begins and ends in the same symbol and has at least three symbols; conversely choose w as its first symbol and x as the nonempty middle. Hence L₁=a(a+b)+a ∪ b(a+b)+b, regular. L₃=a*b*c* is regular. If L₂ were regular, its complement within a*b* would give the nonregular equal-count language. Thus A.

More Regular and Context-Free Languages, Pumping Lemma questions

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