Let $L_1 = \{w \in \{0,1\}^* \mid w\text{ has at least as many occurrences of } (110)\text{'s as } (011)\text{'s}\}$. Let $L_2 = \{w \in \{0,1\}^* \mid w\text{ has at least as many occurrences of } (000)\text{'s as } (111)\text{'s}\}$. Which one of the following is TRUE?

### Analysis of $L_1$: Notice that any transition from a block of consecutive $1$'s to a block of consecutive $0$'s requires the substring $110$ (if preceded by at least two $1$'s), and any transition from $0$ to a block of $1$'s requires $011$ (if followed by at least two $1$'s).

More precisely, in any string $w$, occurrences of $011$ and $110$ alternate:

• An occurrence of $011$ indicates entering a block of at least two $1$'s from a $0$.

• An occurrence of $110$ indicates leaving a block of at least two $1$'s to a $0$.

Because they strictly alternate, the count of $(110)$ and the count of $(011)$ in any string $w$ can differ by at most $1$:

Since the difference between the two counts is bounded by a constant independent of string length, a finite automaton can keep track of the current difference using a finite number of states. Thus, $L_1$ is regular.

---

### Analysis of $L_2$: In $L_2$, occurrences of $000$ and $111$ can overlap arbitrarily within long runs:

• A run of $n$ zeros ($0^n$) contains $n - 2$ occurrences of $000$.

• A run of $m$ ones ($1^m$) contains $m - 2$ occurrences of $111$.

Consider the family of strings $w = 0^n 1^m$. The condition becomes $(n - 2) \ge (m - 2) \implies n \ge m$. Using the Pumping Lemma, if we intersect $L_2$ with the regular language $0^* 1^*$, we get $\{0^n 1^m \mid n \ge m\}$, which requires an unbounded counter and is non-regular. Therefore, $L_2$ is not regular.

Thus, $L_1$ is regular but not $L_2$ (Option A).