Symbolsequenz

Symbolsequenzen werden i​n der Disziplin d​er symbolischen Dynamik m​it Methoden d​er Formalen Sprachen (Grammatiktheorie, Automatentheorie, Komplexitätstheorie) u​nd der Theorie Stochastischer Prozesse untersucht.

Eine Symbolsequenz i​st eine

1. endliche,
2. einseitig-unendliche oder
3. zweiseitig-unendliche

Folge von Symbolen, d. h. von Elementen aus einer endlichen Menge, die Alphabet ${\displaystyle \mathbf {A} }$ genannt wird. Die Menge aller endlich aber beliebig langen Symbolsequenzen aus ${\displaystyle \mathbf {A} }$, die Kleenesche Hülle, wird mit ${\displaystyle \mathbf {A} ^{*}}$ bezeichnet.

Im Fall (1) haben die Symbolsequenzen eine feste endliche Länge ${\displaystyle n}$ und werden als Wort bzw. Block der Länge ${\displaystyle n}$ bezeichnet. Die Menge der Wörter der Länge ${\displaystyle n}$ ist ${\displaystyle \mathbf {A} ^{n}}$. Solche Symbolsequenzen heißen in der Programmierung auch Zeichenketten oder engl. Strings.

Im Fall (2) lassen sich die Symbolsequenzen als Funktionen von ${\displaystyle \mathbb {N} \to \mathbf {A} }$ auffassen, was zu der Schreibweise ${\displaystyle \mathbf {A} ^{\mathbb {N} }}$ führt.

Im allgemeinsten Fall (3) sind Symbolsequenzen Funktionen von ${\displaystyle \mathbb {Z} \to \mathbf {A} }$ und die Menge aller Sequenzen wird ${\displaystyle \mathbf {A} ^{\mathbb {Z} }}$ geschrieben.

In den Fällen (2) und (3) wird die symbolische Dynamik, die den Mengen ${\displaystyle \mathbf {A} ^{\mathbb {N} }}$, bzw. ${\displaystyle \mathbf {A} ^{\mathbb {Z} }}$ entspricht, als voller Shift (engl.: full shift) bezeichnet. Wenn nur Teilmengen dieser Mengen in einer symbolischen Dynamik auftreten, spricht man von subshifts. Ein subshift of finite type liegt dann vor, wenn vom full shift eine Menge verbotener Symbolsequenzen auszuschließen ist, die lediglich eine endliche Menge von Wörtern fester Länge ${\displaystyle n}$ enthalten. In diesem Fall können die Symbolsequenzen von einem endlichen Automaten erzeugt werden.