3
$\begingroup$

Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq L_{3} \subseteq L_{2}$ and both $L_{2} - L_{3}$ and $L_{3} - L_{1}$ are infinite.

My solution to this problem is choosing $L_{1} = \{a\}$ (or some other single word in the language), $L_{3} = \Sigma^{+}$, and $L_{2} = \Sigma^{*}$.

Are these choices valid? I think that $\Sigma^{+} - \{a\}$ is infinite, but I am unsure whether or not $\Sigma^{*} - \Sigma^{+}$ is infinite.

$\endgroup$
  • 6
    $\begingroup$ Do you get to pick $L_1$ and $L_2$? From the way this is worded it looks like $L_1$ and $L_2$ are given and you need to need to find $L_3$. $\endgroup$ – templatetypedef Dec 5 '15 at 2:27
  • 1
    $\begingroup$ Also, $\Sigma^* - \Sigma^+ = \Sigma$ is finite. $\endgroup$ – Yuval Filmus Dec 5 '15 at 2:55
  • $\begingroup$ Hint: Think of $L_1,L_2,L_3$ as sets and ignore that they are languages or regular languages. Are you able to solve the problem in that case? What do you know about the definition of what it means for a set to be infinite? $\endgroup$ – D.W. Dec 5 '15 at 3:04
  • 1
    $\begingroup$ You want to split the infinite regular $L_2-L_1$ in two infinite parts that are both regular. What would you do if $L_2-L_1$ turns out to be $(abb)^*$? And for the general case? $\endgroup$ – phs Dec 5 '15 at 12:44
  • $\begingroup$ @phs - clearly, you split that into two halves by having one half be the odd repetitions, and one the even. In general, see my answer. $\endgroup$ – Daniel Martin Jan 1 '16 at 0:12
8
$\begingroup$

Because regular languages are closed under complement and intersection, $L_2 - L_1$ is regular. Because it's also infinite, it contains words of arbitrarily large lengths.

Therefore, by the pumping lemma, there exist some words $x$, $y$, and $z$ such that the concatenation $x y^k z$ is in $L_2 - L_1$ for all $k \geq 0$.

Now consider the language $L'$ consisting of all words of the form $x y^{2k} z$ - that is, words where the $y$ is repeated an even number of times. Clearly, $L'$ is regular and infinite, and so is $L_2 - L_1 - L'$, since it contains all strings $x y^k z$ where $k$ is odd. Therefore, setting $L_3 = L_1 \cup L'$ satisfies the problem.

$\endgroup$

Your Answer

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