Endliche Automaten und reguläre Ausdrücke

Ein Automat ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.

Ein endlicher Automat (engl. Finite State Machine [FSM]) ist ein Automat, bei dem die Menge der möglichen Zustände endlich ist.

Formal definiert: Ein endlicher Automat ist ein Tupel :

• K ist eine endliche Menge von Zuständen.

• Σ ist ein endliches Alphabet (Menge von Zeichen).

• s0 ∈ K ist der Startzustand (Anfangszustand).

• F ⊆ K ist die Menge der finalen Zustände (Endzustände).

Hierbei verwenden wir, wie an dieser Stelle üblich, die griechischen Buchstaben Σ (Groß-Sigma) und δ (Klein-Delta).

Wenn sie für jeden möglichen Eingabewert definiert ist.

Endliche Automaten dienen zur Modellierung von Berechnungen: Mit jedem Berechnungsschritt geht ein Computer in einen neuen Zustand (Speicherinhalt) über.

Üblicherweise mit einem Doppelkreis.

Es sind die Akzeptoren, die Eingabewerte entgegennehmen, prüfen und dann akzeptieren oder ablehnen.

Ein Akzeptor akzeptiert ein Wort w, wenn er beim Einlesen der einzelnen Zeichen des Wortes jeweils einen geeigneten Übergang enthält und am Ende des Wortes in einem Endzustand steht.

Ein solcher Akzeptor bildet beispielsweise einen Bestandteil eines Compilers, der einen Programmtext analysiert und als syntaktisch korrekt bewertet bzw. Syntaxfehler identifiziert.

Dieser Text beschreibt verschiedene Arten von "Akzeptoren", also Maschinen, die entscheiden, ob eine bestimmte Eingabe akzeptiert wird oder nicht. Die bekannteste Art solcher Maschinen sind endliche Automaten, aber es gibt auch andere Varianten. Der Text erklärt eine spezielle Variante, nämlich den nicht-deterministischen endlichen Automaten (NFA).

Hier eine vereinfachte Erklärung:

1. Deterministischer vs. Nicht-deterministischer Automat:

   • Bei einem deterministischen endlichen Automaten (DFA) gibt es für jede Kombination aus einem Zustand (wo sich der Automat gerade befindet) und einem Eingabewert (das aktuelle Zeichen, das gelesen wird) genau einen nächsten Zustand.

   • Bei einem nicht-deterministischen endlichen Automaten (NFA) kann es für die gleiche Kombination von Zustand und Eingabewert mehrere mögliche nächste Zustände geben. Der Automat "entscheidet" sich dann gewissermaßen, welchen Weg er nimmt.

2. Übergangsrelation statt Übergangsfunktion:

   • In einem NFA wird eine Übergangsrelation anstelle einer Übergangsfunktion verwendet. Das bedeutet, dass für den gleichen Zustand und das gleiche Zeichen verschiedene nächste Zustände möglich sind.

3. Steckenbleiben und Fehlerzustand:

   • Ein NFA kann auch "steckenbleiben", das heißt, es gibt keine gültigen Übergänge mehr, und der Automat erreicht nie einen Endzustand. In diesem Fall wird die Eingabe nicht akzeptiert.

   • Um einen NFA vollständig zu machen, kann man einen "Fehlerzustand" hinzufügen. Wenn der Automat an einer Stelle steckenbleibt, wechselt er in diesen Fehlerzustand. Von dort aus gibt es keine Möglichkeit, einen akzeptierenden Endzustand zu erreichen.

4. Unterschied zwischen vollständigen und unvollständigen Automaten:

   • Ein vollständiger Automat hat für jede mögliche Eingabe einen Übergang definiert.

   • Ein unvollständiger Automat hat nicht für jede Eingabe einen Übergang, und wenn er keine passende Regel findet, bleibt er stehen.

Der Text erklärt also, dass man bei nicht-deterministischen Automaten oft auf eine vollständige Definition der Übergänge verzichtet, weil dies den Automaten unnötig kompliziert machen würde, besonders wenn die zusätzlichen Übergänge sowieso nicht dazu führen, dass das Wort akzeptiert wird. Ein unvollständiger Automat kann aber leicht in einen vollständigen überführt werden, indem man einen Fehlerzustand hinzufügt

• Endliche Automaten mit ε-Kanten sind nicht-deterministische endliche Automaten,

• die zusätzlich Statusübergänge ohne Einlesen eines Zeichens erlauben. (ε ist der griechische Buchstabe Klein-Epsilon). Ein solches „leeres“ Zeichen oder Wort wird als ε dargestellt, die entsprechende Kante als ε-Kante bezeichnet. Oft erlaubt man in solchen Automaten auch Kanten, bei denen mehr als ein Zeichen eingelesen wird.

• DFA (Deterministic Finite Automaton)

• DEA (deterministischer endlicher Automat)

• NFA (Non-deterministic Finite Automaton)

• NEA (nicht-deterministischer endlicher Automat)

• ε-NEA für Automaten mit ε-Kanten

Automaten, die über eine Ja-/Nein-Aussage als Ergebnis hinausgehen und Eingabewerte in Ausgabewerte übersetzen.

Transduktoren werden beispielsweise in einem Compiler verwendet, um eine Zeichenkette einzulesen und ihre Struktur zu analysieren.

Sofern es bei einem Zustand eine andere Kante für ein beliebiges Zeichen a gibt als die 𝜀-Kante, kann beim Einlesen von a sowohl die andere Kante als auch die 𝜀-Kante für den nächsten Schritt gegangen werden. Gibt es keine andere Kante, dann ist die 𝜀-Kante überflüssig und die beiden verbundenen Zustände können zusammengelegt werden.

• Reguläre Ausdrücke beschreiben Muster für Zeichenketten und werden beispielsweise häufig für Suchfunktionen verwendet.

Ein Beispiel: Der reguläre Ausdruck a(b|c)*a beschreibt alle Zeichenketten, die mit einem a beginnen, dann beliebig viele b und c enthalten und schließlich mit einem weiteren a enden. So entspricht beispielsweise die Zeichenkette abbcbca diesem regulären Ausdruck, abbcbc dagegen nicht. Man sagt daher, ein bestimmtes Wort, also eine Zeichenkette, gehört zu der vom regulären Ausdruck definierten Sprache oder eben auch nicht.

Definition „Reguläre Ausdrücke“

Gegeben sei eine als Alphabet bezeichnete Menge Σ (Sigma) von Zeichen. Reguläre Ausdrücke über dem Alphabet Σ sind wie folgt definiert:

• ∅ (leere Menge) ist ein regulärer Ausdruck.

• Jedes Zeichen ai ∈ Σ ist ein regulärer Ausdruck.

• Sind x und y reguläre Ausdrücke, dann sind auch

  • (x|y) (Alternative),

  • xy (Verkettung) und

  • x* (

    Kleenesche Hülle

    , d. h. beliebig häufige Wiederholung von x, einschließlich 0-fach) reguläre Ausdrücke.

• [abc]: eines der Zeichen a, b oder c;

• [0-7]: eine der Ziffern 0 bis 7;

• [A-Za-z]: ein beliebiges Buchstabenzeichen (klein oder groß);

• [A-Za-z0-9]: ein beliebiges Buchstabenzeichen oder eine Ziffer;

• [-A-Z],[A-Z-]: Auswahl enthält auch den Bindestrich '-';

• ?: Ausdruck ist optional;

• +: Ausdruck darf beliebig oft, aber mindestens einmal, vorkommen;

• *: Ausdruck darf beliebig oft, auch überhaupt nicht, vorkommen;

• n: Ausdruck muss genau n-mal vorkommen.

Satz 3.2: Hauptsatz von Kleene

Die durch reguläre Ausdrücke definierten Sprachen sind identisch zu den von endlichen Automaten akzeptierten Sprachen:

Lreg = LDFA

Schubfachprinzip

Das Schubfachprinzip, engl. Pigeon Hole Principle, besagt: Wenn man mehr als n Gegenstände auf n Schubfächer aufteilt, dann enthält mindestens ein Schubfach mehr als einen Gegenstand.

Um zu zeigen, dass bestimmte Sprachen nicht regulär sind und es daher keinen endlichen Automaten gibt, der sie akzeptiert.

1. Pumping-Lemma für reguläre Sprachen:

• Das Pumping-Lemma ist ein wichtiges Werkzeug, um zu zeigen, dass eine Sprache nicht regulär ist.

• Es besagt grob, dass für jede reguläre Sprache ein sogenanntes "Pumping-Längen" nnn existiert. Für jedes Wort der Sprache, das länger als nnn ist, muss das Wort in drei Teile xyzxyzxyz aufgeteilt werden können, wobei:

  1. xyizxy^izxyiz auch in der Sprache liegen muss, für jedes i≥0i \geq 0i≥0.

  2. yyy nicht leer ist.

  3. Die Länge von xyxyxy höchstens nnn beträgt.

Wenn du eine Sprache findest, die diese Eigenschaften nicht erfüllt, kannst du daraus schließen, dass sie nicht regulär ist.

Beispiel: Die Sprache L={anbn∣n≥0}L = \{a^n b^n \mid n \geq 0 \}L={anbn∣n≥0} ist nicht regulär. Wenn man versucht, das Pumping-Lemma darauf anzuwenden, stellt man fest, dass man das Wort w=anbnw = a^n b^nw=anbn nicht in drei Teile xyzxyzxyz aufteilen kann, sodass xyizxy^izxyiz für beliebige Werte von iii immer noch in der Sprache liegt.

Eine Sprache ist nicht regulär, wenn sie von einem endlichen Automaten nicht akzeptiert werden kann. Das bedeutet, dass kein endlicher Automat (egal ob deterministisch oder nicht-deterministisch) existiert, der alle Wörter der Sprache korrekt erkennt und akzeptiert.

• Endliche Automaten sind Maschinen, die durch Zustandsübergänge reguläre Sprachen akzeptieren.

• Reguläre Ausdrücke sind formale Beschreibungen von Mustern, die reguläre Sprachen definieren.

• Beide sind äquivalent, beschreiben aber das Problem auf unterschiedliche Weise: Automaten durch ihre Verarbeitung, reguläre Ausdrücke durch ihre formale Beschreibung.

Im Allgemeinen unbegrenzt viele, da man einen endlichen Automaten auf viele Weisen variieren kann, ohne die akzeptierte Sprache zu verändern.