Automatic sequence

An automatic sequence is an infinite word characterized by a finite automaton. There are two equivalent definitions.

Automaton point of view

Let "q" be an integer, and "A"=("E",φ,"e") be a deterministic automaton where
*"E" is the finite set of states
*φ : "E"× [0,"q"-1] →"E" is the transition function
*$ein\; E$ is the initial statealso let "A" be a finite set, and π:"E"→"A" a projection towards "A".

For each "n", take "m"("n") = π(φ("e",$n\text{'}$)) where $n\text{'}$ is "n" written in base "q". Then the sequence "m" = "m"(1)"m"(2)"m"(3)... is called a "q"-automatic sequence.

ubstitution point of view

Let σ be a morphism of the free monoid "E"^* with $sigma(E)subseteq\; E^q$, and $ein\; E$ such that σ("e") begins by "e". Let also be "A" and π as before. Then if $m\text{'}$ is a fixpoint of σ, that is to say $m\text{'}$ = σ($m\text{'}$), then "m" = π($m\text{'}$) is a "q"-automatic sequence over "A".

Examples

The Thue-Morse sequence is automatic: take "E"="A"={0,1}, "e"=0, π=id, and σ such that σ(0)=01, σ(1)=10; we get the fixpoint 01101001100101101001011001101001... , which is in fact the Thue-Morse word.