In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid.
[1] Let f be an endomorphism of the free monoid A∗ on an alphabet A with the property that there is a letter a such that f(a) = as for a non-empty string s: we say that f is prolongable at a.
It is clearly a fixed point of the endomorphism f: the unique such sequence beginning with the letter a.
[2][3] In general, a morphic word is the image of a pure morphic word under a coding, that is, a morphism that maps letter to letter.
The n-th term in such a sequence can be produced by a finite-state automaton reading the digits of n in base k.[1] A D0L system (deterministic context-free Lindenmayer system) is given by a word w of the free monoid A∗ on an alphabet A together with a morphism σ prolongable at w. The system generates the infinite D0L word ω = limn→∞ σn(w).