Prove that if $L$ is regular, then $f(L)$ is regular too

Question

Prove that if $L$ is regular, then $f(L)$ is regular too.

$\Sigma_1$ and $\Sigma_2$ are two arbitrary alphabets, $f$ is a function that maps every symbol of $\Sigma_1$ to an element in $\Sigma_2$, i.e., $f : \Sigma_1 \to \Sigma_2$.

$L_1$ is a regular language, $f^*(s_1s_2...) = f(s_1)f(s_2)...$ where $s_1s_2...$ is a string, and

$$f^*(L_1) = \bigcup f^*(w), w\in L_1.$$

The function $F(L_2)$ has following form:

$$F(L_2) = \{w\in \Sigma_1^* \;|\; f^*(w) \in L_2\}$$

1. Could you show that if $L_2$ is regular, then $F(L_2)$ is regular too.

2. Are this statements is correct:

   • $f^*(F(L_2)) \subseteq L_2$;
   • $L_2 \subseteq f^*(F(L_2))$;
   • $L_1 \subseteq F(f^*(L_1))$.

Answer 1

If $L$ is a regular language, then it is defined by an extended (right-) regular grammar (see https://en.wikipedia.org/wiki/Regular_grammar) $G$, whose rules are of the form:

• $B\to w$, for $B$ a nonterminal symbol, $w\in \Sigma^*$ (a string of terminal symbols);
• $B\to wC$, for $B,C$ nonterminal symbols, $w\in \Sigma^*$;
• $B\to\varepsilon$.

Given $f\colon\Sigma_1\to\Sigma_2^*$, use $f$ to create a new grammar $G'$ over $\Sigma_2$ by replacing every terminal symbol $a\in\Sigma_1$ in the righthand side of a $G$-rule with $f(a)$. The resulting grammar is easily seen to be an extended right-regular grammar, and the language it defines is $f^{*}(L)$; so $f^{*}(L)$ is also regular.

$f^*$ is a (monoid) homomorphism $\Sigma_1^*\to\Sigma_2^*$. The function $F$ maps languages to languages. For any $L\subseteq\Sigma_2^*$, $F(L) = f^{*{-1}}(L)\subseteq\Sigma_1^*$ is the inverse image of $L$ under $f^*$. If $L$ is regular, then so $F(L)$, because the regular languages are closed under inverse homomorphisms.

Your last three statements are equivalent to these reformulations, and they are true, only sometimes true, and true respectively, for any function, not just $f^*$:

1. $f^*(f^{*{-1}}(L_2)) \subseteq L_2$: always true;
2. $L_2 \subseteq f^*(f^{*{-1}}(L_2))$: true only if $L_2\subseteq image(f^*)$;
3. $L_1 \subseteq f^{*{-1}}(f^*(L_1))$: always true.