Is $L_1 = \{w ∈ {0,1}∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$ regular?

Question

Let $L_1 = \{w ∈ \{0,1\}^∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$.

Let

$L_2=\{w ∈ \{0,1\}^∗ | \text{ w has at least as many occurrences of (000)’s as (111)’s}\}$.

Which one of the following is TRUE?

1. $L_1$ is regular but not $L_2$
2. $L_2$ is regular but not $L_1$
3. Both $L_2$ and $L_1$ are regular
4. Neither $L_1$ nor $L_2$ are regular

---

My attempt :

We cannot have two $110$'s in a string without a $011$ or vice verse.

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$. Yes, if a binary string starts with $11$, it can never have more no. of $011$ than $110$.

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.

But, L2 is not regular.(I guessed).

Can you explain please, with pumping lemma or other way to prove/disprove classes of given languages?

Answer 1

To reiterate your argument about $L_1$: Any string not ending in $11$ is in $L_1$, and a string ending in $11$ is in $L_1$ iff it starts with $11$. So as a regular expression, $$L_1=(\{0,1\}^*(0|01))\mid 11\{0,1\}^*11\mid 111\mid 11\mid 1\mid \epsilon $$

$L_2$ on the other hand is not regular. Assume it is and let $n$ be its pumping length. Consider $1^n0^n\in L_2$ can be written as $uvw$ with $|uv|\le n$ (so consisting only of $1$'s) and $|v|\ge 1$ and such that among others $uv^3w\in L_2$. But that has more occurances of $111$ than of $000$.

Answer 2

$L_2$ is can be easily seen to be non-regular using the Myhill-Nerode theorem.

Your automaton for $L_1$ seems to be right, so the language is regular, but it would probably need a more explicit argument that the automaton actually recognizes $L_1$ before it constitutes a proof.

I suggest annotating the states with all combinations of "last two symbols seen" and "difference between number of 110s and 001s ever seen" that can happen in that state. Then it's a purely local matter to verify that those invariants are preserved by every transition.