Suppose that $L$ is a language.

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

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

  • 1
    $\begingroup$ @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$. $\endgroup$ – ttnick May 17 '18 at 18:26
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. May 17 '18 at 22:04
  • $\begingroup$ Just to avoid all misunderstandings, I've included both interpretations of the question. $\endgroup$ – reinierpost May 18 '18 at 9:19
  • $\begingroup$ 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? $\endgroup$ – Hendrik Jan May 18 '18 at 11:49
  • $\begingroup$ @HendrikJan "But what would ${}^-L^*$ mean?" That seems completely hypothetical and not relevant to the question. $\endgroup$ – 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^*\,.$$


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.