Normal numbers and finite automata

BECHER, VERÓNICA; HEIBER, PABLO

THEORETICAL COMPUTER SCIENCE

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2013 vol. 477 p. 109 - 116

0304-3975

We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are finite automata augmented with an output transition function such that the automata input/output behaviour is injective; they are also known as injective finite-state transducers). As a corollary we obtain V.N. Agafonov´s theorem on the preservation of normality on subsequences selected by finite automata.