Automatic sequence

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

Automaton point of view

Let A=(E,φ,e) be an automaton where

• E is the finite set of states
• φ : E×[0,q-1]→E is the transition function
• e$\in$E is the initial state

let also A be a finite set, and π:E→A a projection towards A.

For each n, take m(n) = π(φ(e,n')) where n' is n written in base q. Then the sequence m = m(1)m(2)m(3)... is an automatic sequence.

Substitution point of view

Let σ be a morphism over E, σ : E→E^q, and e$\in$E such that σ(e) begins by e. Let also be A and π as before. Then if m' is a fixpoint of σ, that is to say m' = σ(m'), then m = π(m') is an automatic sequence.

Exemples

The Thue-Morse sequence is automatic : take E={0,1}, e=0, and σ such that σ(0)=01, σ(1)=10, we get 01101001100101101001011001101001...