Prove that a regular language $L$ exists satisfying $L_1 \subseteq L \subseteq L_2$ and $L - L_1$ and $L_2 - L$ are both infinite.

Question

Let $L_1, L_2$ be regular languages, with $L_1 \subseteq L_2$ and $L_2 - L_1$ infinite. Prove that a regular language $L$ exists satisfying $L_1 \subseteq L \subseteq L_2$ and $L - L_1$ and $L_2 - L$ are both infinite.

The set of regular languages is closed under set-difference, so $L_2 - L_1$ is an infinite regular language. Let $p$ be the pumping length of $L_2 - L_1$, and let $w$ be some string in L with $|w| > p$. Then by the pumping lemma, there exists a splitting of $w$, namely $w = xyz$ with $|y| > 0$, $|xy| \leq p$, and $xy^iz \in L_2 - L_1$ for $i \geq 0$. Now, define $L$ to be $L_1 \cup \{xy^iz : i \geq 0 \}$. Clearly, $\{xy^iz : i \geq 0 \}$ is a regular language, and thus $L$ is a regular language. Further, since $\{xy^iz : i \geq 0 \}$ is an infinite language, it must be that $L - L_1$ is infinite.

The above is what I've come up with so far. As for showing that $L_2 - L$ is infinite, could I posit some string $x \in L_2 - L_1$ with $x \neq w$ and $|x| > p$ whose pumpable middle portion does not equal $y$?

Answer 1

What happens if you use $x(yy)^iz$?

Answer 2

We can rephrase your question as follows. Given an infinite regular language $R$, decompose it into two disjoint infinite regular languages $R_1,R_2$. Parikh's theorem shows that the set of lengths of words in $R$ is eventually periodic, say with period $m$. Since $R$ is infinite, this means that for some $a$ it is the case that $R$ has a word of length $km+a$ for all $k \geq 0$. We can take $R_1$ as the subset of $R$ consisting of words whose lengths are of the form $2km+a$.

Kirill's answer is a low-tech version of the same idea.