Regular expressions and closure properties of regular languages
We know that regular expressions represent exactly the regular languages and we know that regular languages are closed under several operations. This exercise is about finding regular expressions for the languages after the application of one of such operations.
Given as input regular expressions r_1 and r_2, representing respectively languages L_1 and L_2, by construction (r_1)+(r_2), (r_1)(r_2), and (r_1)^* represent respectively the languages L_1\cup L_2, L_1L_2, and L_1^*. What about the other operations that preserve regularity?
(complement) Given as input a regular expression r, representing the language L, give an algorithm to find the regular expression representing the language \overline{L}. What is the asymptotic cost of the algorithm proposed as a function of the number of symbols in r?
(intersection) Given as input regular expressions r_1 and r_2, representing respectively languages L_1 and L_2, give an algorithm to find a regular expression representing the language L_1\cap L_2. What is the asymptotic cost of the algorithm proposed as a function of the number of symbols in r_1 and r_2?
(reverse) Given as input a regular expression r, representing the language L, give an algorithm to find a regular expression representing the language L^R. What is the asymptotic cost of the algorithm proposed as a function of the number of symbols in r?
(homomorphism) Given as input a regular expression r, representing the language L, and a homomorphism \sigma, give an algorithm to find a regular expression representing the language \sigma(L).
(inverse homomorphism) Given as input a regular expression r, representing the language L, and a homomorphism \sigma, give an algorithm to find a regular expression representing the language \sigma^{-1}(L).