1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
4
  • $\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 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 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 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 at 9:45

Your Answer

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

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