Symbolsequenz

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Symbolsequenzen werden in der Disziplin der symbolischen Dynamik mit Methoden der Formalen Sprachen (Grammatiktheorie, Automatentheorie, Komplexitätstheorie) und der Theorie Stochastischer Prozesse untersucht.

Eine Symbolsequenz ist eine

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

Folge von Symbolen, d. h. von Elementen aus einer endlichen Menge, die Alphabet genannt wird. Die Menge aller endlich aber beliebig langen Symbolsequenzen aus , die Kleenesche Hülle, wird mit bezeichnet.

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

Im Fall (2) lassen sich die Symbolsequenzen als Funktionen von auffassen, was zu der Schreibweise führt.

Im allgemeinsten Fall (3) sind Symbolsequenzen Funktionen von und die Menge aller Sequenzen wird geschrieben.

In den Fällen (2) und (3) wird die symbolische Dynamik, die den Mengen , bzw. 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 enthalten. In diesem Fall können die Symbolsequenzen von einem endlichen Automaten erzeugt werden.