⟸ Go Back ⟸

Exercise 7 (Homework 1).

(homomorphism, theory of languages)

Homomorphisms II – basic properties

Given a morphism \sigma:\Sigma^*\to\Sigma^* and languages L,L_1,L_2\subseteq \Sigma^*, justify your answers to the following questions.

1. Does homomorphism on languages distribute over concatenation? That is, does it hold that \sigma(L_1L_2)=\sigma(L_1)\sigma(L_2)?
2. Does homomorphism and exponentiation of languages commute? That is, does it hold that \sigma(L^n)=\sigma(L)^n for any positive integer n?
3. Does homomorphism and union of languages commute? That is, does it hold that \sigma(L_1\cup L_2)= \sigma(L_1)\cup\sigma(L_2)?
4. Does homomorphism of languages and the Kleene star commute? That is, does it hold that \sigma(L^*)=\sigma(L)^*?
5. Does homomorphism and reverse of languages commute? That is, does it hold that \sigma(L^R)=\sigma(L)^R?
6. Does homomorphism and complementation of languages commute? That is, does it hold that \sigma(\overline{L})=\overline{\sigma(L)}?
7. Does the identity homomorphism on a language act as the identity on its words? That is, does it hold that whenever \sigma(L)=L, then \sigma(x)=x for all x in L?