Quelltext der Seite Symbolsequenz

{{Belege fehlen}}

'''Symbolsequenzen''' werden in der Disziplin der [[symbolische Dynamik|symbolischen Dynamik]] mit Methoden der [[Formale Sprache|Formalen Sprache]]n ([[Formale Grammatik|Grammatiktheorie]], [[Automatentheorie]], [[Komplexitätstheorie]]) und der Theorie [[Stochastischer Prozess]]e untersucht.

Eine Symbolsequenz ist eine 

# endliche, 
# einseitig-unendliche oder 
# zweiseitig-unendliche 

Folge von [[Symbol]]en, d.&nbsp;h. von Elementen aus einer endlichen Menge, die [[Alphabet]] <math>\mathbf{A}</math> genannt wird. Die Menge aller endlich aber beliebig langen Symbolsequenzen aus <math>\mathbf{A}</math>, die [[Kleenesche Hülle]], wird mit <math>\mathbf{A}^*</math> bezeichnet. 

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

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

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

In den Fällen (2) und (3) wird die symbolische Dynamik, die den Mengen <math>\mathbf{A}^\mathbb{N}</math>, bzw. <math>\mathbf{A}^\mathbb{Z}</math> 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 <math>n</math> enthalten. In diesem Fall können die Symbolsequenzen von einem [[endlicher Automat|endlichen Automaten]] erzeugt werden.

[[Kategorie:Stochastik]]
[[Kategorie:Theoretische Informatik]]
[[Kategorie:Compilerbau]]