string homomorphism is defined in formal language theory as:
A string homomorphism (often referred to simply as a homomorphism in formal language theory) is a string substitution such that each character is replaced by a single string. That is, f(a)=s , where s is a string, for each character a.
and has a clearer and equivalent algebraic definition:
String homomorphisms are monoid morphisms on the free monoid, preserving the empty string and the binary operation of string concatenation.
The first definition shows that in formal language theory, string homomorphism is defined as a special case of substitution, which is defined as:
Let L be a language, and let Σ be its alphabet. A string substitution or simply a substitution is a mapping f that maps characters in Σ to languages (possibly in a different alphabet).
Does string substitution have a clearer and equivalent definition, similar to the one for string homomorphism in terms of monoid morphism of the free monoid?
If yes, does that equivalent definition of substitution still consider homomorphism as a special case?
Thanks.
Best Answer
Yes. Let $A$ and $B$ be alphabets. Then $A^*$ and $B^*$ are (free) monoids, but ${\cal P}(B^*)$ is also a (non-free) monoid under the usual product of languages. Now, a substitution is a monoid morphism from $A^*$ to ${\cal P}(B^*)$.
Homomorphisms are a special case if you identify $B^*$ as the submonoid of ${\cal P}(B^*)$ consisting of the singletons.