##### Gate 2014 Set 2 Question

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 is A.But I Don't Know How?Please Someone Explain this to me.

L1 can interpreted as language in which no. of (110) >= no. of (011)

// here just take simple examples like (ε, 110, 0110, 11011 ,...)

we can make dfa for it

and L2 can interpreted as language in which no. of (000) >= no. of (111)

// here we need memory to memorise , so CFL can be but not regular