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 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
  • e\in E is the initial state

also let 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 of the free monoid E* with \sigma(E)\subseteq 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 a q-automatic sequence over A.

[edit] 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.