HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Find a regular language that is "infinitely between" two other regular languages

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#50335, answer score: 8

Revisions (0)

No revisions yet.