Morphic word

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.
Every automatic sequence is morphic.
Definition.
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". The word
is a pure morphic or pure substitutive word. Note that it is the limit of the sequence "a", "f"("a"), "f"("f"("a")), "f"("f"("f"("a"))), ...
It is clearly a fixed point of the endomorphism "f": the unique such sequence beginning with the letter "a". In general, a morphic word is the image of a pure morphic word under a coding.
If a morphic word is constructed as the fixed point of a prolongable "k"-uniform morphism on "A"∗ then the word is "k"-automatic. The "n"-th term in such a sequence can be produced by a finite state automaton reading the digits of "n" in base "k".
D0L system.
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 ω = lim"n"→∞ σ"n"("w"). Purely morphic words are D0L words but not conversely. However, if ω = "u"ν is an infinite D0L word with an initial segment "u" of length |"u"| ≥ |"w"|, then "z"ν is a purely morphic word, where "z" is a letter not in "A".