2
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You could still get all of $L_2 - L_1$. $\endgroup$ – Yuval Filmus Sep 27 '14 at 7:23
  • $\begingroup$ @YuvalFilmus How? $xyz$ wouldn't be in it, or am I wrong? $\endgroup$ – Kirill Sep 27 '14 at 7:23
  • $\begingroup$ On second thought, you're right. $\endgroup$ – Yuval Filmus Sep 27 '14 at 7:24
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.