The GATE Grind

GATE 2014 CS (CS2) – Question 46

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

L₁ consists of binary strings with at least as many occurrences of 110 as of 011. L₂ consists of binary strings with at least as many occurrences of 000 as of 111. Which is TRUE?

  1. L₁ regular, L₂ not regular
  2. L₂ regular, L₁ not regular
  3. Both regular
  4. Neither regular

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) L₁ regular, L₂ not regular

Explanation

For overlapping occurrences, #110−#011 equals the indicator that the string starts with11 minus the indicator that it ends with11. This bounded boundary property is regular. In contrast, intersecting L2 with0^(a+2)1^(b+2) imposes a≥b, an unbounded counting comparison; it is not regular. Thus **L1 regular,L2 not,A**.