Symbol sequence

from Wikipedia, the free encyclopedia

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

  1. finite,
  2. unilateral-infinite or
  3. 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.

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 .

In case (2) the symbol sequences can be understood as functions of , which leads to the notation .

In the most general case (3) symbol sequences are functions of and the set of all sequences is written.

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 .