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.

1Comment
shivani @shivani1234
4 Oct 2017 05:31 pm

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