1
$\begingroup$

Where can I find a proof of this? Thanks!

$\endgroup$

migrated from cstheory.stackexchange.com May 14 '13 at 11:59

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 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$ – Alejandro Sazo 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
7
$\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$
5
$\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