Grundlagen der Zeichenketten, Alphabete und Automaten

Zeichenkette

Eine Zeichenkette (String) ist eine geordnete Folge beliebiger Länge (wenn auch endlich) von Elementen, die Zugehörigkeit zu einem Alphabet besitzen. Im Allgemeinen ist eine Zeichenkette eine Folge von Buchstaben, Zahlen oder anderen Zeichen (Symbolen). In der Mathematik werden üblicherweise die Buchstaben w, x, y, z verwendet, um sich auf Zeichenketten zu beziehen.

Aus Sicht der Programmierung kann eine Zeichenkette aus allen endlichen Kombinationen aller zur Verfügung stehenden Zeichensätze bestehen.

Alphabet

Ein Alphabet ist eine geordnete Menge von Symbolen. Eine Sprache ist die Gruppe mit einer bestimmten Reihenfolge der Grapheme, die verwendet werden, um die Sprache darzustellen, die als Kommunikationssystem in der Mathematik dient. Es ist eine endliche geordnete Menge von Symbolen.

Sprache

Eine formale Sprache ist ein Wort (String) endlicher Länge, das aus einem Alphabet (der Menge der Zeichen) gebildet wird. Der Name Sprache ist gerechtfertigt, weil die Strukturen, die Regeln bilden (Dramaturgie) und die semantische Interpretation (Sinn) sind.

Formale Sprachen können auf vielfältige Weise angegeben werden, darunter:

• Zeichenketten, die durch eine formale Grammatik erzeugt werden
• Zeichenketten, die durch einen regulären Ausdruck erzeugt werden
• Zeichenketten, die durch einen Automaten als Turing-Maschine akzeptiert werden

Regulärer Ausdruck

Auch als Muster bezeichnet, ist ein regulärer Ausdruck eine Möglichkeit, reguläre Sprachen darzustellen. Er wird mit Hilfe von Alphabetzeichen konstruiert, die speziell die Sprache der regulären Ausdrücke definieren, und verwendet die Kleene-Stern-Notation.

Verkettung

Die Verkettung ist der Vorgang, mit dem zwei Zeichen zu einem String oder einer String-Form zusammengefügt werden. Sie können auch zwei Strings verketten oder ein Zeichen mit einer Kette, um eine größere Kette zu bilden.

Kleene-Stern A*

Wenn A eine Sprache über einem Alphabet ist, wird die Stern-Kleene-Hülle wie folgt definiert: A* = U?_n=0Aⁿ. Wörter, die in einer Zeichenkette 0, 1, ...? erscheinen können.

Positive Hülle A⁺

Sie ist wie folgt definiert: A⁺ = U?_n=1Aⁿ, was bedeutet, dass das Zeichen, das folgt, mindestens einmal auftreten sollte.

Finite State Machine (FSM)

Der endliche Automat ist ein mathematisches Modell für ein System mit diskreten Ein- und Ausgängen. Das System kann sich in jeder von einer endlichen Anzahl von Konfigurationen oder Zuständen befinden. Der Zustand des Systems fasst die Informationen in Bezug auf frühere Eingaben zusammen und ist notwendig, um das Verhalten des Systems für spätere Eingaben zu bestimmen. Es wird gesagt, dass eine reguläre Sprache durch einen endlichen Automaten akzeptiert wird.

Deterministischer endlicher Automat (DFA)

Ein DFA besteht aus einer Reihe von Zuständen und einer Reihe von Übergängen von Zustand zu Zustand, die beim Eingeben von Symbolen aus einem Alphabet auftreten.

Für jedes Eingabesymbol gibt es nur einen Übergang von jedem Zustand. Er hat einen Anfangszustand und einen oder mehrere akzeptierende Zustände. Ein DFA ist mit einem gerichteten Graphen verbunden, der als Übergangsdiagramm bekannt ist.

Definition der Automaten

AFD = (Q, ?, A, q₀, f)

Wobei:

• Q: Die endliche Menge der Zustände
• ?: Das endliche Eingabealphabet
• A: Die Übergangsfunktion oder Übergangstabelle
• q₀: Der Anfangszustand
• f: Die Menge der Endzustände

Endliche Automaten befinden sich auf der untersten Ebene der Hierarchie von Maschinen und Sprachen.

Eine Anwendung ist der Bau eines Compilers. Ein Compiler muss Schichten erkennen, die Strings und Symbole sind, um das Quellprogramm als Darstellungen der einzelnen Objekte zu betrachten. Zum Beispiel Variablennamen, numerische Konstanten und Schlüsselwörter. Diese Mustererkennungsaufgabe wird vom Lexer des Compilers behandelt.