Minimal Automaton for Multiplying and Translating the Thue-Morse Set

Abstract

The Thue-Morse set $\mathcal{T}$ is the set of those non-negative integers whose binary expansions have an even number of $1$'s. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word

$${\tt 0110100110010110\cdots},$$

which is the fixed point starting with ${\tt 0}$ of the word morphism ${\tt 0\mapsto 01}$, ${\tt 1\mapsto 10}$. The numbers in $\mathcal{T}$ are commonly called the evil numbers. We obtain an exact formula for the state complexity of the set $m\mathcal{T}+r$ (i.e. the number of states of its minimal automaton) with respect to any base $b$ which is a power of $2$. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all $2^p$-expansions of the set of integers $m\mathcal{T}+r$ for any positive integers $p$ and $m$ and any remainder $r\in\{0,\ldots,m{-}1\}$. The proposed method is general for any $b$-recognizable set of integers.