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?



1 Answer 1


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.

  • $\begingroup$ Thanks. How is the product of languages defined? Is it union? $\endgroup$
    – Tim
    Jun 21, 2020 at 12:05
  • $\begingroup$ A language is a subset of $B^*$, that is, an element of ${\cal P}(B^*)$. The product of two languages $L$ and $L'$ is the language $LL' = \{uu' \mid u \in L, u' \in L'\}$. $\endgroup$
    – J.-E. Pin
    Jun 21, 2020 at 12:37

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.