5
$\begingroup$

In closure properties, I got confused between substitution and morphism.

1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a different alphabet), that is, $f(a) = L_a$. Does that means to replace a letter with a language? Or replace 1 letter from a set of alphabets with 1 letter another set of alphabets?

2) According to Wikipedia, string homomorphism means to replace each letter with a single string, that is, $f(a) = s$, where $s$ is a string. What does 'a single string' mean? Does this mean the letter 'a' may be replaced by a string such as 'owl'? A webpage says that homomorphism is a group maps, which make me even more confused. What's the difference with substitution?

3) I thought that if $\left| f(a) \right|=1$, it's called morphism. Then this is not a string but only a letter. Are morphism and homomorphism the same thing?

I am a beginner and really confused. Hope somebody can help me clear this confusion, as well as the difference in proving the closure properties of substitution, homomorphism, and morphism. Your knowledge and help are very appreciated.

$\endgroup$
3
$\begingroup$

Indeed morphism and homomorphism are the same in formal language theory. They are letter-to-string mappings $h:\Sigma \to \Delta^*$, and then extended to string-to-string mappings $h:\Sigma \to \Delta^*$ in a morphic way: $h(\varepsilon) = \varepsilon$, and $h(xy) = h(x)h(y)$ for strings $x,y\in \Sigma^*$.

A substitution is a letter-to-language mapping, which is likewise extended to a string-to-language mapping. By identifying a singleton language $\{x\}$ to the string $x$, morphisms are seen as special case of substitutions.

A letter-to-letter morphism is sometimes called a coding.

$\endgroup$
  • $\begingroup$ Just to complete Hendrik Jan's excellent answer: a (homo)morphism is actually a monoid morphism from the monoid $\Sigma^*$ to the monoid $\Delta^*$ and a substitution is a monoid morphism from the monoid $\Sigma^*$ to the monoid $\mathcal{P}(\Sigma^*)$ of all languages over $\Sigma^*$, with concatenation as the product operation. $\endgroup$ – J.-E. Pin Apr 8 '15 at 15:43

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.