Q. 45
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:
