Note that every homomorphism h can be regarded as a substitution h' where if h(_) = w, h'(_) = {w}. While homomorphisms map each letter to a unique string, a general substitution provides numerous optional strings for transforming each letter. For this reason substitutions may be regarded as “non-deterministic” homomorphisms.
Every homomorphism has a finite description, but a substitution need not have a finite description. If the languages associated with letters are infinite, a finite description of the substitution may be impossible.
| Previous slide | Next slide | Back to first slide | View graphic version |