S 1 aS 1b generates L₁ and S 2 abS 2 generates L₂. P says L₁ is regular; Q says L₂ is regular. Which is true?

GATE 2016 CS (CS2) – Question 27

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

$S_1\to aS_1b\mid\epsilon$ generates L₁ and $S_2\to abS_2\mid\epsilon$ generates L₂. P says L₁ is regular; Q says L₂ is regular. Which is true?

Both P and Q
P true, Q false
P false, Q true
Both false

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) P false, Q true

Explanation

L₁ is {aⁿbⁿ:n≥0}, nonregular by the pumping lemma because arbitrarily many a’s must be matched by b’s. L₂ is $(ab)^*$, directly regular. Thus P is false and Q true, C.

More Regular and Context-Free Languages, Pumping Lemma questions

GATE 2016 CS (CS2) Q28 – L₁ is regular, L₂ context-free, L₃ recursive and L₄ recursively enumerable. Which hold? I:…
GATE 2016 CS (CS2) Q53 – L 1=\anbmcn+m:m,n1\ and L 2=\anbnc2n:n1\. Which holds?
GATE 2017 CS (CS2) Q14 – L₁,L₂ are context-free and R is regular. Which are correct? I: L₁∪L₂ is context-free. II:…
GATE 2017 CS (CS2) Q50 – L₁=aᵖ:p prime, L 2=\anbmc2m:n,m0\, L 3=\anbnc2n:n0\, L₄=aⁿbⁿ:n≥1. Which hold? I: L₁…
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…

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