HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Difference between substitution, morphism, and homomorphism

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
morphismsubstitutionhomomorphismdifferencebetweenand

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#41123, answer score: 5

Revisions (0)

No revisions yet.