|Abstract of Paper|
On selection functions that do not preserve normality
by Wolfgang Merkle and Jan Reimann
The subsequence selected from a sequence R(0)R(1)... by a language L is the sequence of all bits R(n+1) such that the prefix R(0)...R(n) is in L. By a result of Agafonoff, a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is neither preserved by linear languages nor by languages recognized by deterministic push-down automata with unary stack alphabet. In fact, for both types of languages it is possible to select a constant sequence from a normal one.