# GATE | GATE-CS-2014-(Set-2) | Question 65

Let L1 = {w ∈ {0,1}^{∗}| w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = { ∈ {0,1}^{∗}| w has at least as many occurrences of (000)’s as (111)’s}.

Which one of the following is TRUE?**(A)** L1 is regular but not L2**(B)** L2 is regular but not L!**(C)** Both L2 and L1 are regular**(D)** Neither L1 nor L2 are regular**Answer:** **(A)****Explanation:** **L1 is regular**

let us consider the string 011011011011

In this string, number of occurrences of 011 are 4 but when we see here 110 is also occurred and the number of occurrence of 110 is 3.

Note that if i add a 0 at the last of string we can have same number of occurrences of 011 and 110 so this string is accepted. We can say if the string is ending with 011 so by appending a 0 we can make 110 also.

Now string2: 110110110110 in this number of occurrences of 110 is 4 and 011 is 3 which already satisfy the condition

So we can observe here that whenever 110 will be there string will be accepted

So with this idea we can build an automata for this. Therefore, it is regular.

Attention reader! Don’t stop learning now. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in **GATE Test Series Course**.

Learn all **GATE CS concepts with Free Live Classes** on our youtube channel.