Symbol sequence

Sequences of symbols are examined in the discipline of symbolic dynamics using methods of formal languages ( grammar theory , automaton theory , complexity theory ) and the theory of stochastic processes .

A sequence of symbols is a

finite,
unilateral-infinite or
bilateral infinite

Sequence of symbols , d. H. of elements from a finite set called the alphabet . The set of all finite but arbitrarily long symbol sequences , the Kleen's envelope , is denoted by. ${\ displaystyle \ mathbf {A}}$ ${\ displaystyle \ mathbf {A}}$ ${\ displaystyle \ mathbf {A} ^ {*}}$

In case (1), the symbol sequences have a fixed finite length and are referred to as a word or block of length . The set of words of length is . Such symbol sequences are also called character strings in programming . Strings . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle \ mathbf {A} ^ {n}}$

In case (2) the symbol sequences can be understood as functions of , which leads to the notation . ${\ displaystyle \ mathbb {N} \ to \ mathbf {A}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathbb {N}}}$

In the most general case (3) symbol sequences are functions of and the set of all sequences is written. ${\ displaystyle \ mathbb {Z} \ to \ mathbf {A}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathbb {Z}}}$

In cases (2) and (3) the symbolic dynamics that the quantities respectively, corresponding to a full shift (engl .: full shift hereinafter). If only subsets of these sets occur in a symbolic dynamic, one speaks of subshifts . A subshift of finite type occurs when a number of forbidden symbol sequences that only contain a finite number of words of fixed length are to be excluded from the full shift . In this case the symbol sequences can be generated by a finite automaton . ${\ displaystyle \ mathbf {A} ^ {\ mathbb {N}}}$ ${\ displaystyle \ mathbf {A} ^ {\ mathbb {Z}}}$ ${\ displaystyle n}$