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


1 Answer 1


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^*$.

  • $\begingroup$ 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... $\endgroup$
    – Eric_
    May 31, 2021 at 9:27
  • $\begingroup$ 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'$. $\endgroup$
    – Nathaniel
    May 31, 2021 at 9:30
  • $\begingroup$ 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? $\endgroup$
    – Eric_
    May 31, 2021 at 9:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathaniel
    May 31, 2021 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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