patternMinor
Do Kleene star and complement commute?
Viewed 0 times
starcommutecomplementandkleene
Problem
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$?
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$?
Solution
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.
Context
StackExchange Computer Science Q#21544, answer score: 7
Revisions (0)
No revisions yet.