What does $\overline{L}^*$ signify?

Suppose that $L$ is a language.

• What does $\overline{L}^*$ signify?

• Is $\overline{L^*}$ the same as $(\overline{L})^*$?

• @YuvalFilmus I think the question should have been "Is $\overline{L^\ast} = \overline{L}^\ast$?" The answer here would be "no" since for $L = \varnothing$ we have $\overline{L^\ast} = \Sigma^+ \neq \Sigma^\ast = \overline{L}^\ast$. – ttnick May 17 '18 at 18:26
• There's no difference between $\overline{L}^*$ and $(\overline{L})^*$; they are the same expression, just with parentheses added. It's like asking whether there is a difference between $(1+2)$ vs $1+2$; or a difference between $(1+2)+3$ vs $1+2+3$. Is this really what you wanted to ask? – D.W. May 17 '18 at 22:04
• Just to avoid all misunderstandings, I've included both interpretations of the question. – reinierpost May 18 '18 at 9:19
• I do think the original question about the meaning of $\overline L^*$ makes perfect sense. We apply two unary operators (star and complement) to a language, both written on separate positions (right-above and above). There is no a priory order they are evaluated. What makes it hard to see the problem is that even typing it in LaTeX chooses the interpretation. But what would $\bar{} L^*$ mean? – Hendrik Jan May 18 '18 at 11:49
• @HendrikJan "But what would ${}^-L^*$ mean?" That seems completely hypothetical and not relevant to the question. – David Richerby May 18 '18 at 18:04

For any language $L$ over alphabet $\Sigma$,
• $\overline{L} = \Sigma^*\setminus L$ is the complement of $L$: the set of $\Sigma$-strings not in $L$;
• $L^*$ is the Kleene closure of $L$: the set of strings $w\in\Sigma^*$ such that we can write $w=w_1\dots w_k$ for some $k\geq 0$ such that each $w_i\in L$. For example, if $L$ is the set of English words, then correcthorsebatterystaple is in $L^*$.
Now, $\overline{L}^*$ is something-star, where "something" is $\overline{L}$. That is, it's the Kleene closure of the complement of $L$: the set of all strings $w\in\Sigma^*$ that can be written $w_1\dots w_k$ such that each $w_i$ is not in $L$. Essentially, we read left-to-right, so you parse "$\overline{L}$" before you reach the star.
Conversely, $\overline{L^*}$ is something-complement, where "something" is $L^*$, the Kleene closure of $L$. That is, it is the set of all strings that cannot be written $w_1\dots w_k$ where each $w_i\in L$.
These are not necessarily the same languages. For example, consider $\Sigma=\{1\}$ and $L=\{11\}$. Then $1\in\overline{L}$, so $\overline{L}^*=\Sigma^*$. However, $$\overline{L^*} = \overline{\{1^i\mid i\text{ is even}\}} = \{1^i\mid i\text{ is odd}\}\neq\Sigma^*\,.$$