gotchaMinor
Difference between substitution, morphism, and homomorphism
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.
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.
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.