# Is the concatenation of a non-regular CFL and a complement of a regular upper-set always non-regular?

Let $$L_1$$ be a non-regular CFL. Let $$L_2$$ be a regular language. Assume that $$\left(L_1\right)^{*} \subseteq L_2$$. I'm looking at $$L_3 = \left( L_1 \right) ^{*} \circ \overline{L_2}$$. Is $$L_3$$ always non-regular? I can find multiple examples of it being non-regular, yet none of it being regular.

Edit: $$\overline{L_2} \neq \emptyset$$.

Consider the language $$L = \{uv\mid u, v\in\Sigma^*, |u|=|v|\wedge u\neq v\}$$. I claim that $$L$$ is context-free, it is not regular (a simple pumping lemma proof can do the trick), but $$L^*$$ is regular, without being equal to $$\Sigma^*$$, so that means that $$L^*\overline{L^*}$$ is regular and satisfies your conditions.

Now let's show that if we denote $$L'= (\Sigma\Sigma)^*\setminus\left(\bigcup\limits_{a\in\Sigma}a^*\right)\cup \{\varepsilon\}$$ (words of even length, not composed of the same letter), then $$L^*=L'$$:

• the inclusion $$\subseteq$$ is the easiest, since words of $$L$$ are of even length, and are not composed of the same letter. We added $$\varepsilon$$ to $$L'$$ by definition of the Kleene star;

• let's prove by induction that $$L'\subseteq L^*$$:

• consider $$w\in L'$$; if $$w = \varepsilon$$, then $$w\in L^*$$, if $$|w| = 2$$, then $$w\in L$$ (because it contains two different letters), so $$w\in L^*$$;

• suppose the result proved for words of length up to a certain $$2n\in\mathbb{N}$$, and consider $$w\in L'$$ of length $$2n+2$$. If $$w\in L$$, then trivially, $$w\in L^*$$. Otherwise, since $$|w|$$ is even, then $$w = uu$$, with $$u\in\Sigma^*$$, $$u$$ containing different letters.

• If $$|u|$$ is even, then it means that $$u \in L'$$
• Otherwise, $$u = u_1u_2…u_{2k+1}$$, and we can show that $$uu = xy$$ verifying $$x,y\in L'$$ (with either $$x = u_1…u_{2k}$$ and $$y = u_{2k+1}u$$ or $$x=uu_1$$ and $$y = u_2…u_{2k+1}$$).

In all cases, we can use the induction hypothesis to show that $$w\in L^*$$.

• Could you elaborate a bit more on why $L^{*}$ is regular? I can see its an upper-set of $\left\{ \left( a b \right) ^{*} \right\}$, but it also contains other forms of strings... – Eric_ May 31 at 9:27
• The language $L' = (\Sigma\Sigma)^*\setminus\left(\bigcup\limits_{a\in\Sigma}a^*\right)\cup \{\varepsilon\}$ is regular because $(\Sigma\Sigma)^*$ regular, and so are $a^*$ for $a\in\Sigma$ and $\{\varepsilon\}$. If we use closure properties of regular languages, then it shows that $L'$ is regular. $L^*$ is regular because I proved it equal to $L'$. – Nathaniel May 31 at 9:30
• I see that now. But, are you assuming $\left| \Sigma \right| = 1$ ? If not (assuming for example that $\left| \Sigma \right| = 2$) then $L^{'}$ should exclude $\left\{ b^{*} \right\}$ as well, right? – Eric_ May 31 at 9:39
• I am not assuming $|\Sigma| = 1$ otherwise $L$ would be empty, that's why I wrote $\bigcup\limits_{a\in\Sigma} a^*$, to exclude all words composed of the same letter, whatever the letter is. Here, the notation $a$ is a free variable. – Nathaniel May 31 at 9:45