# Do Kleene star and complement commute?

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

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

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$.)
• $\varepsilon\in L^*$ for any language $L$ so neither of these two claims is possible. – David Richerby Feb 12 '14 at 10:44