Minimal automaton for multiplying and translating the Thue-Morse set (Q2040011)

Summary: 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 \[\mathtt{0110100110010110}\cdots,\] which is the fixed point starting with \(0\) of the word morphism \(\mathtt{0\mapsto 01}\), \(\mathtt{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.