For any given alphabet $\Sigma$, find the language $L$ that satisfies $L = (\Sigma L)^C$

Question

I have an exercise and I don't know how to solve it. The problem statement is as follows:

Prove, for any alphabet $\Sigma$, there is a unique language $L$ that satisfies $L = (\Sigma L)^C$. What language is it?

From set theory I know that $A^C = U - A$, therefore $(\Sigma L)^C = \Sigma^* - \Sigma L$ (where $\Sigma^*$ is the set of all words over an alphabet $\Sigma$) . I can't think of anything that can help me here using this.

Answer 1

The condition $(\Sigma L)^c = L$ can also be written, by taking complements on both sides, as $\Sigma L = L^c$. It follows that, for every word $u \in \Sigma^*$ and every letter $a \in \Sigma$, $$ u \in L \iff au \in L^c \quad (1) $$ Indeed, if $u \in L$, then $au \in \Sigma L = L^c$ and if $au \in L^c = \Sigma L$, then $u \in L$.

Now, since $\Sigma L$ does not contain the empty word $\varepsilon$, one must have $\varepsilon \in L$. Using (1), it is now easy to prove (by induction on the length of the words) that the words of even length are necessarily in $L$, and those of odd length are necessarily in $L^c$. It follows that $L$ is necessarily equal to the language $(\Sigma^2)^*$ of words of even length. It just remains to verify that indeed, this language is a solution of the equation $\Sigma L = L^c$.

Answer 2

A word $w\in\Sigma^*$ is in $(\Sigma L)^C$ iff it is not of the form $\alpha u$ for any $\alpha\in\Sigma$ and $u\in L$. Since we want to have $L=(\Sigma L)^C$, we want an $L$ such that $w\in L$ iff $w\ne\alpha u$ for any $\alpha\in\Sigma$ and $u\in L$. In other words, $L$ must contain $\epsilon$, since that is clearly not of the form $\alpha u$, and the non-empty words in $L$ must have the form $\alpha u$ for some $\alpha\in\Sigma$ and $u\notin L$: if $\epsilon\ne w\in\Sigma^*$, then $w\in L$ iff peeling off the first character of $w$ leaves a word not in $L$. This means that $L$ should satisfy the equation

$$L=\{\epsilon\}\cup\Sigma\left(L^C\right)\,.$$

Suppose that $L$ is such a language.

• Show that $\Sigma\cap L=\varnothing$, so that $\Sigma\subseteq L^C$.
• Show that $L=\{w\in\Sigma^*:|w|\text{ is even}\}$.

When you’ve done this, you’ll have shown that there is at least one such language, but you’ll still have to prove that it’s unique. HINT: If $L'\ne L$ is another such language, consider a $w\in L'\setminus L$ of minimal length.