patternMinor
Find a regular language that is "infinitely between" two other regular languages
Viewed 0 times
infinitelylanguagesregularlanguagetwobetweenthatfindother
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#50335, answer score: 8
Revisions (0)
No revisions yet.