Proof of a Known Claim About Languages

Question

I would like to know how to prove that there is no non-trivial language $L$ that satisfies the following condition:

$${\large \left(\overline{L}\right)^* = \overline{L^*}}$$

"Non-trivial" is intended to exclude languages of the form $\sigma^*$ where $\sigma \subset\Sigma$. This includes the empty language and $\Sigma^*$ as special cases.

Answer 1

As user21820 points out in the comments, $\varepsilon \in \overline{L}^{\,*}$ and $\varepsilon \notin \overline{L^*}$. This turns out to be the only reliable difference: or in other words, attempts to fix this allow in non-trivial counterexamples.

Consider these variants:

• $L^*$ is the language of words formed by concatenating 0 or more words of $L$;
• $L^+$ is the language of words formed by concatenating 1 or more words of $L$;
• $L^* \backslash \{\varepsilon\}$ is the language of non-empty words formed by concatenating 1 or more words of $L$.

If $\varepsilon \in L$ then $L^+ = L^*$; otherwise $L^+ = L^* \backslash \{\varepsilon\}$. The three variants differ only by whether or not they contain $\varepsilon$, and all three are closed under concatenation of non-empty words.

If we take $L^\sim$ to denote any of the variants under the constraint that we can't assume the presence or absence of $\varepsilon$ then we can consider whether $\overline{L}^{\,\sim} = \overline{L^\sim}$.

Suppose that the language $L$ satisfies this modified condition, and that word $\varepsilon \ne w \in L$. Then $L^\sim$ includes all words of the form $w^n$ ($n > 0$), so $\overline{L^\sim}$ includes no words of the form $w^n$ ($n > 0$), and therefore $\overline{L}^{\,\sim}$ may include no word of the form $w^n$ ($n > 0$), whence $\overline{L}$ may include no word of the form $w^n$ ($n > 0$), so $L$ must include all words of the form $w^n$ ($n > 0$). We could say that $L$ is point-wise closed under $^\sim$.

This leads the way to a simple counterexample. Consider $L = (a|ab)^\sim$. $L$ contains all words over $\{a, b\}$ which start with an $a$ and don't have $bb$ as a substring. So $\overline{L} = b(a|b)^*|(a|b)^*bb(a|b)^*$ possibly unioned with $\{\varepsilon\}$. Observe that $L = L^\sim$ and $\overline{L} = \overline{L}^{\,\sim}$, so either $\overline{L^\sim} = \overline{L} = \overline{L}^{\,\sim}$ or the equality breaks down solely due to $\varepsilon$ being present on one side but not on the other.

So for specific fixes:

• $\overline{L}^{\,*} \backslash \{\varepsilon\} = \overline{L^*}$: both sides are explicitly prohibited from containing $\varepsilon$, so we can take $L = (a|ab)^*$ or $L = (a|ab)^+$.
• $\overline{L}^{\,*} = \overline{L^*} \cup \{\varepsilon\}$: both sides explicitly contain $\varepsilon$, so we can take $L = (a|ab)^*$ or $L = (a|ab)^+$.
• $\overline{L}^{\,+} = \overline{L^*}$: the RHS doesn't contain $\varepsilon$, so in order that the LHS not contain $\varepsilon$ we take $\varepsilon \in L$, i.e. $L = (a|ab)^*$.
• $\overline{L}^{\,*} = \overline{L^+}$: the LHS contains $\varepsilon$, so in order that the RHS contain it we take $\varepsilon \notin L$, i.e. $L = (a|ab)^+$.

---

Out of interest, there is another interesting closure property which is implied by the condition (in any variant).

Suppose $n >1$, $w^n \in L$, and $w \notin L$. ($w \ne \varepsilon$ follows trivially). Then $w \in \overline{L}$, so $w^n \in \overline{L}^{\,\sim}$, giving a contradiction to $w^n \notin \overline{L^\sim} \impliedby w^n \in L^\sim \impliedby w^n \in L$. So we see that $L$ is point-wise closed under an operation we might call anti-Kleene-star, or nth roots.