Exercici 11 (Tasca 1).
(theory of languages,
hard exercise)
L=\overline{\Sigma L}
Demostreu que, per a qualsevol alfabet \Sigma, hi ha un únic llenguatge L que satisfà L=\overline{\Sigma L}. Quin és aquest llenguatge?
Ajut
Doneu una expressió alternativa per a L. Conté L el mot buit \lambda? Si un mot de L és de la forma aw, amb a pertanyent a \Sigma, on pertany w? A L o a \overline L? Un cop obtingueu la nova expressió, deixeu-la en funció de L i resolgueu la recurrència.