3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$

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.