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,179 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.
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.
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.[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
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]
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 ω = 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]
Honkala, Juha (2010). "The equality problem for purely substitutive words". In
Berthé, Valérie; Rigo, Michel (eds.). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge:
Cambridge University Press. pp. 505–529.
ISBN978-0-521-51597-9.
Zbl1216.68209.
Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press.
ISBN978-0-521-18071-9.
Zbl1221.68183.