Disjunctive sequence

From Wikipedia, the free encyclopedia

A disjunctive sequence is an infinite sequence (over a finite alphabet of characters) in which every finite string appears as a substring. For instance, the binary Champernowne sequence

formed by concatenating all binary strings in lexicographical order, clearly contains all the binary strings and so is disjunctive. (The spaces above are not significant and are present solely to make clear the boundaries between strings).

Any normal sequence (a sequence in which each string of equal length appears with equal frequency) is disjunctive, but the converse is not true. For example, letting 0ⁿ denote the string of length n consisting of all 0's, consider the sequence

obtained by splicing exponentially long strings of 0's into a lexicographical ordering of all binary strings. Most of this sequence consists of long runs of 0's, and so it is not normal, but it is still disjunctive.