Are regular languages closed under inverse homomorphism?

Question

Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \varphi(\varepsilon) & = & \varepsilon \\ \varphi(w\sigma ) & = & \varphi(w)\varphi(\sigma ), \textrm{ for any } w \in \Sigma ^*, \sigma \in \Sigma \end{eqnarray*} Any function $\varphi:\Sigma^* \rightarrow \Delta^*$ defined in this way from a function $\varphi: \Sigma \rightarrow \Delta^*$ is called a homomorphism. We can extend this definition to languages as follows: for any language $L$ and homomorphism $\varphi$, let $$\varphi(L)=\{\varphi(w) : w\in L\}.$$

Are regular languages are closed under inverse homomorphism?

Answer 1

Short algebraic proof. Let $M$ be a monoid recognizing a language $L$ of $A^*$. By definition, this means that there is a monoid homomorphism $\eta: A^* \to M$ and a subset $P$ of $M$ such that $L = \eta^{-1}(P)$.

Let $\varphi: B^* \to A^*$ be a monoid homomorphism. Then $\eta \circ \varphi: B^* \to M$ is also an homomorphism. Further, the equality $\varphi^{-1}(L) = \varphi^{-1}(\eta^{-1}(P)) = (\eta \circ \varphi)^{-1}(P)$ shows that the language $\varphi^{-1}(L)$ is also recognized by $M$.

Now a well-known result states that a language is regular if and only if it is recognized by some finite monoid. It follows immediately that if $L$ is regular, then $\varphi^{-1}(L)$ is also regular.

Answer 2

Yes, regular languages are closed under inverse homomorphism.

Here is a proof. We start with a DFA of $L$, $X$. To prove that $\varphi^{-1}(L)$ is regular, we will construct a DFA, $Y$ for $\varphi^{-1}(L)$.

$$ X = (Q,\Sigma,\delta_X,q_0,F)$$

So our construction will be as follows:

$$ Y = (Q,\Delta,\delta_Y,q_0,F)$$

Where:

$$\delta_Y(q,w) = \hat{\delta_X}(q,\varphi(w))$$

Or in other words, the transition in Y on w is the result of the sequences of transition that X makes on the string of symbols $\varphi(w)$. So all we need to do now is prove this transition. To do this we will induct on $|w|$. Our hypothesis being $\hat{\delta_Y}(q,w) = \hat{\delta_X}(q,\varphi(w))$.

Base: When $w = \epsilon$:

$$q_0 = \delta_Y(q_0,\epsilon) = \delta_X(q_0,\varphi(\epsilon)) = \delta_X(q_0,\epsilon) = q_0$$

Inductive Step: First let $w = \sigma s$:

$$\hat{\delta_Y}(q_0,w) = \hat{\delta_Y}(\delta_Y(q_0,\sigma),s)$$

Then by our inductive hypothesis:

$$\hat{\delta_Y}(\delta_Y(q_0,\sigma),s) = \hat{\delta_Y}(\delta_X(q_0,\varphi(\sigma)),s)$$

Now by our DFA definition above:

$$\hat{\delta_Y}(\delta_X(q_0,\varphi(\sigma)),s) = \hat{\delta_X}(\delta_X(q_0,\varphi(\sigma)),\varphi(s))$$

Pulling the $\delta$ back in:

$$\hat{\delta_X}(\delta_X(q_0,\varphi(\sigma)),\varphi(s)) = \hat{\delta_X}(q_0,\varphi(\sigma)\varphi(s))$$

Now by the definition of homomorphism:

$$\hat{\delta_X}(q_0,\varphi(\sigma)\varphi(s)) = \hat{\delta_X}(q_0,\varphi(\sigma s)) = \hat{\delta_X}(q_0,\varphi(w))$$