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.

You can help expand this article with text translated from the corresponding article in French. (June 2021) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic to this template: there are already 6,166 articles in the main category, and specifying|topic= will aid in categorization. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is Content in this edit is translated from the existing French Wikipedia article at [[:fr:Mot morphique]]; see its history for attribution. You may also add the template {{Translated|fr|Mot morphique}} to the talk page. For more guidance, see Wikipedia:Translation.

Every automatic sequence is morphic.^[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. The word

${\displaystyle asf(s)f(f(s))\cdots f^{(n)}(s)\cdots \ }$

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.^[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.^[1]

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.^[1]

• The Thue–Morse sequence is generated over {0,1} by the 2-uniform endomorphism 0 → 01, 1 → 10.^[4][5]
• The Fibonacci word is generated over {a,b} by the endomorphism a → ab, b → a.^[1][4]
• The tribonacci word is generated over {a,b,c} by the endomorphism a → ab, b → ac, c → a.^[5]
• The Rudin–Shapiro sequence is obtained from the fixed point of the 2-uniform morphism a → ab, b → ac, c → db, d → dc followed by the coding a,b → 0, c,d → 1.^[5]
• The regular paperfolding sequence is obtained from the fixed point of the 2-uniform morphism a → ab, b → cb, c → ad, d → cd followed by the coding a,b → 0, c,d → 1.^[6]

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→∞ σⁿ(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]

• Cutting sequence
• Lyndon word
• Hall word
• Sturmian word