Automatic sequence

From Wikipedia, the free encyclopedia

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

[edit] Automaton point of view

Let be q an integer, and A=(E,φ,e) be an deterministic automaton where

• E is the finite set of states
• φ : E×[0,q-1]→E is the transition function
• eE 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 called a q-automatic sequence.

[edit] Substitution point of view

Let σ be a morphism over E, σ : E→E^q, and eE 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.

[edit] Exemples

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