4
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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
    Commented Feb 12, 2014 at 10:43

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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$.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ $\varepsilon\in L^*$ for any language $L$ so neither of these two claims is possible. $\endgroup$
    – David Richerby
    Commented Feb 12, 2014 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.