1
$\begingroup$

Where can I find a proof of this? Thanks!

$\endgroup$
4
  • 5
    $\begingroup$ Have you tried google? You will find this. $\endgroup$
    – A.Schulz
    May 14 '13 at 12:01
  • $\begingroup$ Write down a regular expression for your language, apply the homomorphism to it and you are done. $\endgroup$
    – vonbrand
    May 14 '13 at 23:08
  • $\begingroup$ Isn't he asking about the proof that regular languages are closed under homomorphisms? $\endgroup$ May 15 '13 at 13:37
  • $\begingroup$ Wow, that's a ... short question. What have you tried, where did you get stuck? $\endgroup$
    – Raphael
    Aug 16 '13 at 11:26
8
$\begingroup$

First of all, homomorphism is a special case of substitution. Now define the homomorphism as a substitution $h$ that replaces each symbol $a$ in an alphabet $\Sigma$ for a string $h(a) \in \Gamma^*$, where $\Gamma$ can be another alphabet (they can perfectly be the same). Formally the homomorphism $h(\epsilon) = \epsilon$ and for all strings in $ \Sigma^*$, $$h(a_1a_2\ldots a_n) = h(a_1)h(a_2)\ldots h(a_n)$$

Then you are near to proving the closure. Try induction over the number of operands (unions, concatenations, stars) in the regular expression that represents the language $L$. Base step: $h(\epsilon)=\epsilon$ for all $a \in \Sigma^*$, $h(a)$ is a string over $\Gamma^*$ and $h(\emptyset) = \emptyset$. The induction hyphotesis says that if $L$ is regular, then $h(L)$ is regular. The inductive step has three cases: $L$ as a union of $A$ and $B$ ($A \cup B$), $L$ as the concatenation of $A$ and $B$ ($L=AB$) or $L = A^*$. Then you should be able to finish the proof.

$\endgroup$
6
$\begingroup$

It is a special case of a more general result: rational subsets of monoids are closed under morphisms.

The set of rational subsets of a monoid $M$ is the smallest set of subsets of $M$ containing the finite subsets and closed under union, product and star. The product of two subsets $X$ and $Y$ of $M$ is the set $XY = \{ xy \mid x \in X, y \in Y \}$ and $X^*$ is the submonoid generated by $X$.

Now if $f: M \rightarrow N$ is a monoid morphism and $R$ is a rational subset of $M$, then $f(R)$ is a rational subset of $N$. If further $f$ is surjective, then for each rational subset $S$ of $N$, there exists a rational subset $R$ of $M$ such that $f(R) = S$.

This is Proposition 2.2, p. 48 of the book by J. Berstel, Transductions and context-free languages, Teubner (1979). This book is out of print, but the first four chapters can be found here.

$\endgroup$
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\}.$$

If $L$ is a regular language, then we can construct a Regular Expression, $X$, for $L$. Now we must prove $\varphi(L)$ is regular, which means we must construct a Regular Expression $Y$ for $\varphi(L)$. Then we must prove that the set of strings accepted by $Y$ is a subset of those accepted by $\varphi(L)$, and the set of strings accepted by $\varphi(L)$ is a subset of those accepted by $Y$, thus proving they are equivilent.

Construct: First is our construction. The way that we will create our Regular Expression is simple. Apply $\varphi(L)$ to each symbol in $X$. This will give us the regular expression $Y$.

$Y \subseteq \varphi(L)$: We can easily see any string accepted by the regular expresion $Y$ must be in $\varphi(L)$. All accepted by $Y$ must first follow the original rules of $X$, but each symbol in $X$ has now been processed by $\varphi$ and thus each string accepted by $Y$ must be accepted by $\varphi(L)$.

$ \varphi(L) \subseteq Y$: Once again this is not that hard. All strings that are accepted by $\varphi(L)$ must first follow the regular expression $X$, but rather than use the old symbols, will have them put through $\varphi$ first. This is the definition of $Y$ so easy to see.

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