I am having hard time solving the following problem.

Are there any languages for which $$ \overline{L^*} = (\overline{L})^* $$

Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = \{a\}$ and L = $\Sigma^*$, I get that $L^* = L$ and that $\overline{L^*} = \emptyset$. For the right side I get $\overline{L} = \emptyset$ and $(\overline{L})^* = \emptyset$. Thus, both sides are equal.

Is it true that $\emptyset^* = \emptyset$?

  • 1
    $\begingroup$ No, $\emptyset^* = \{\varepsilon\}$, since you can make the empty word by concatenating zero or more strings from $\emptyset$ (specifically, by concatenating zero of them). $\endgroup$ – David Richerby Feb 12 '14 at 10:43

Hint: The star of a language always contains the empty string. The complement of a language containing the empty string never does. With that in mind, look at the left and the right hand sides of your proposed equality.


Hint: I can think of an example in which both sides are $\emptyset$, and another one in which both are $\Sigma^*$.

(This hint works only if you allow $\emptyset^* = \emptyset$. That's the case if you define $L^* = \bigcup_{x \in L} x^*$. The usual definition is $L^* = \sum_{n \geq 0} L^n$.)

  • $\begingroup$ $\varepsilon\in L^*$ for any language $L$ so neither of these two claims is possible. $\endgroup$ – David Richerby Feb 12 '14 at 10:44

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.