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?


2 Answers 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)$$


$$\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))$$


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.

  • $\begingroup$ Can a similar proof be written for the closure of context-free languages under inverse homomorphisms? $\endgroup$
    – Lynn
    Oct 14, 2015 at 23:00
  • $\begingroup$ No. But a similar proof works for star-free languages, for instance. $\endgroup$
    – J.-E. Pin
    Oct 15, 2015 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.