Exercise 11 (Homework 1).
(theory of languages,
hard exercise)
L=\overline{\Sigma L}
Prove that, for every alphabet \Sigma, there is a unique language L such that L=\overline{\Sigma L}. What is this language?
Hint
Give an alternative expression for L. Does L contain the empty word \lambda? If a word in L is of the form aw, with a\in \Sigma, is w in L or in \overline L? Once obtained the new expression, rewrite it as a function of L and resolve the recurrence relation.