Normality and automata (Q494059)

The contribution discusses the compressibility of normal words by various finite-state devices. Roughly speaking, a normal word is an infinite word such that each given block of \(n\) letters occurs (in the limit) as often as each other block of \(n\) letters. This notion of normality is based on the classical notion for numbers established by Émile Borel. Compressibility is defined via a finite-state transducer (with potentially other facilities such as stacks or counters) that receives the input and transforms it into a string containing essentially the same information (bounded-to-one) in ultimately fewer symbols for the prefixes (adjusted for alphabet size). It is demonstrated that neither deterministic nor nondeterministic finite-state transducers can compress normal words. This result also does not depend on the real-time property (i.e., whether \(\varepsilon\)-transitions are permitted or not). Similarly, adding a single counter does not improve the situation and normal words are still not compressible. Since two counters are Turing-complete if \(\varepsilon\)-transitions are permitted, the first compressibility results is obtained. However, even with several counters real-time transducers cannot compress normal words, so the boundary here is clearly the ability to produce output without consuming input. With a single stack and a counter the device becomes powerful enough to compress normal words, whereas it is unclear whether this is also the case for deterministic pushdown transducers (i.e., those with just a single stack). Nondeterministic pushdown transducers and non-real-time transducers again are powerful enough to yield compressions of normal words so that the boundary could either be the presence of the stack or a stack together with some form of nondeterminism. In addition, the authors investigate selection from normal words by means of either prefixes, suffixes, or both. Selection constructs a new word from the given infinite word \(w\) by selecting certain positions in it and disregarding others. In selection via prefix a regular language \(L\) essentially determines whether a position is taken or not. More precisely, the position \(i\) is selected if and only if the prefix of \(w\) up to but not including \(i\) is in \(L\). Suffix selection works similarly given a regular language of infinite words. It is shown that both selection via prefix and selection via suffix preserve the normality of the word, whereas both-sided selection does not. The paper is well written and very self-contained. All major constructions are first presented in a nice overview before the technical details are shown. A background in automata theory, more specifically, regular languages and finite-state transducers, is required to understand the contribution but that basic knowledge can be obtained from any undergraduate course or textbook.