Homomorfismes II – propietats bàsiques

Donat un homomorfisme \sigma:\Sigma^*\to\Sigma^* i llenguatges L,L_1,L_2\subseteq \Sigma^*, justifiqueu les vostres respostes a les preguntes següents.

Distribueix l’homomorfisme de llenguatges sobre la concatenació? És a dir, es compleix \sigma(L_1L_2)=\sigma(L_1)\sigma(L_2)?
Commuten l’homomorfisme i l’exponenciació de llenguatges? És a dir, es compleix \sigma(L^n)=\sigma(L)^n per qualsevol natural n?
Commuten l’homomorfisme i la reunió de llenguatges? És a dir, es compleix \sigma(L_1\cup L_2)= \sigma(L_1)\cup\sigma(L_2)?
Commuten l’homomorfisme de llenguatges i l’estrella de Kleene? És a dir, es compleix \sigma(L^*)=\sigma(L)^*?
Commuten l’homomorfisme i el revessat de llenguatges? És a dir, es compleix \sigma(L^R)=\sigma(L)^R?
Commuten l’homomorfisme i la complementació de llenguatges? És a dir, es compleix \sigma(\overline{L})=\overline{\sigma(L)}?
Actua l’homomorfisme identitat sobre un llenguatge com la identitat sobre els seus mots? És a dir, es compleix \sigma(x)=x per a tot x a L si \sigma(L)=L?

Altres enllaços