Language-theoretic complexity of disjunctive sequences

A sequence over an alphabet ∑ is called disjunctive if it contains all possible finite strings over ∑ as its substrings. Disjunctive sequences have been recently studied in various contexts. They abound in both category and measure senses. In this paper we measure the complexity of a sequence x by the complexity of the language P(x) consisting of all prefixes of x. The languages P(x) associated to disjunctive sequences can be arbitrarily complex. We show that for some disjunctive numbers x the language P(x) is context-sensitive, but no language P(x) associated to a disjunctive number can be context-free. We also show that computing a disjunctive number x by rationals corresponding to an infinite subset of P(x) does not decrease the complexity of the procedure, i.e. if x is disjunctive, then P(x) does not have an infinite context-free subset. This result reinforces, in a way, Chaitinʹs thesis (1969) according to which perfect sets, i.e. sets for which there is no way to compute infinitely many of its members essentially better (simpler/quicker) than computing the whole set, do exist. Finally we prove the existence of the following language-theoretic complexity gap: There is no x ϵ ∑w such that P(x) is context-free but not regular. If S(x), the set of all finite substrings of a sequence x ϵ ∑w, is slender, then the set of all prefixes of x is regular, that is P(x) is regular if and only if S(x) is slender.