The GATE Grind

GATE 2014 CS (CS2) – Question 25

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

Let $L_1=\{a^n:n\ge0\}$ and $L_2=\{b^n:n\ge0\}$. I: $L_1L_2$ is regular. II: $L_1L_2=\{a^nb^n:n\ge0\}$. Which is correct?

  1. Only I
  2. Only II
  3. Both I and II
  4. Neither I nor II

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Only I

Explanation

Independent concatenation gives a*b*={aⁿbᵐ:n,m≥0}, which is regular. There is no requirement that n=m, so it is not the equal-count language{aⁿbⁿ}. Therefore **only I,A**. Regular languages are closed under concatenation.