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.
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
asf(s)f(f(s)) … f(n)(s) …
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.[1] [2] 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.
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.
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). 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.[7]
. M. Lothaire . Applied combinatorics on words . . Encyclopedia of Mathematics and Its Applications . 105 . Cambridge . . 2005 . 0-521-84802-4 . 1133.68067 . registration .
. M. Lothaire . Algebraic combinatorics on words . With preface by Jean Berstel and Dominique Perrin . Reprint of the 2002 hardback . Encyclopedia of Mathematics and Its Applications . 90. Cambridge University Press . 2011 . 978-0-521-18071-9 . 1221.68183 .