# Zdeněk Frolík

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

$asf(s)f(f(s))\cdots f^{(n)}(s)\cdots \$ is a pure morphic or pure substitutive word. 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.

## Examples

• The Thue–Morse sequence is generated over {0,1} by the 2-uniform endomorphism 0 → 01, 1 → 10.
• The Fibonacci word is generated over {a,b} by the endomorphism aab, ba.
• The tribonacci word is generated over {a,b,c} by the endomorphism aab, bac, ca.
• The Rudin–Shapiro sequence is obtained from the fixed point of the 2-uniform morphism aab, bac, cdb, ddc followed by the coding a,b → 0, c,d → 1.
• The regular paperfolding sequence is obtained from the fixed point of the 2-uniform morphism aab, bcb, cad, dcd followed by the coding a,b → 0, c,d → 1.