Q3.2 · Endliche Automaten

Reale Automaten wirken von außen oft wie Blackboxes: Eine Eingabe wird gemacht, im Inneren geschieht Verarbeitung, und am Ende erscheint eine Ausgabe oder Reaktion. Diese EVA-Sicht ist als Einstieg hilfreich, reicht aber für die Modellierung noch nicht aus. Das Automatenmodell macht sichtbar, welche inneren Zustände für diese Verarbeitung unterschieden werden müssen.

Beim Schritt vom realen System zum mathematischen Modell werden Material, Bauweise und Oberflächendesign ausgeblendet. Beibehalten werden nur Zustände, Eingaben, Übergänge und die Start-/Endzustandsidee. Zustände speichern dabei genau die Information über bisherige Eingaben, die für den nächsten Schritt relevant ist.

Beispielhaft kann eine Laborstation mit Zugangscode modelliert werden: Die Regeln liegen zuerst in Alltagssprache vor, müssen dann aber in Eingaben, Zustände, Übergänge und Endzustände übersetzt werden. Modellieren heißt hier: äußere Details weglassen und die fachlich relevante Zustands- und Übergangslogik behalten.

Die Beispiele der Seite haben unterschiedliche Rollen: Der Zugangscode verbindet Q3.1 mit der Sprache L(A), die gerade Anzahl von 1en zeigt Zustandsbedeutung im Minimalmodell, das Zahlenschloss markiert den Wechsel zum Transduktor, reguläre Muster zeigen Ausdrucksstärke und Grenzen, und der NEA vertieft die Idee mehrerer möglicher Wege.

Die folgenden Konventionen dienen als Leseschlüssel. So kannst du Zustandsdiagramme und Übergangstabellen systematisch lesen, bevor komplexere Beispiele folgen.

Aus Sicht formaler Sprachen liest der Automat ein Eingabewort Zeichen für Zeichen; die Übergangsfunktion legt fest, wie das bisher Gelesene im aktuellen Zustand zusammengefasst wird.

Zustände wirken dabei als begrenztes Gedächtnis: Bei einem Zugangscode muss der Automat nicht das ganze Eingabewort speichern, sondern nur relevanten Fortschritt wie Kennbuchstabe schon gelesen, Anzahl gelesener Binärziffern, letztes Zeichen 0 und ob ein Fehlerzustand erreicht wurde.

Ein deterministischer endlicher Automat ist ein Akzeptor: Er erkennt eine formale Sprache, indem er ein Eingabewort Zeichen für Zeichen liest und am Ende über akzeptiert oder verworfen entscheidet. Deterministisch bedeutet: Zu jeder Kombination aus Zustand und Eingabesymbol gibt es genau einen Folgezustand.

Damit entsteht die erkennende Sicht auf Q3.1: Dort wurden zulässige Wörter mit Grammatikregeln erzeugt; hier entscheidet ein Automat für ein gegebenes Eingabewort, ob es zu seiner Sprache L(A) gehört.

Beispiel: gerade Anzahl von 1en

Am gezeigten Automaten bedeutet z0: bisher wurde eine gerade Anzahl von 1en gelesen. z1 bedeutet entsprechend: bisher wurde eine ungerade Anzahl von 1en gelesen. Der aktuelle Zustand ist hier das begrenzte Gedächtnis des Automaten.

• 1 wechselt zwischen z0 und z1 (Parität kippt).
• 0 lässt den Automaten im aktuellen Zustand (Parität bleibt).
• z0 ist Endzustand: akzeptiert werden genau Eingabewörter mit gerader Anzahl von 1en.

Wortprüfung und Sprache L(A)

Ein Eingabewort ist ein Wort über dem Eingabealphabet Σ, also eine endliche Folge von Symbolen aus Σ. Der Trace zeigt die Zustandsfolge beim Lesen. Akzeptanz wird erst nach vollständiger Verarbeitung des Eingabeworts entschieden.

Beispiel Zugangscode: Σ = {A, B, 0, 1}. Eingabewörter über diesem Alphabet können gültig oder ungültig sein. Gültig sind hier genau die Eingabewörter, die mit A oder B beginnen, dann mindestens zwei Binärziffern enthalten, mit 1 enden und keine Teilfolge 00 besitzen. Diese gültigen Eingabewörter bilden die Sprache L(A).

• akzeptiert: Nach dem letzten Symbol wird ein Endzustand erreicht.
• verworfen: Nach dem letzten Symbol ist kein Endzustand erreicht.
• Sprache L(A): Menge aller Eingabewörter, die A akzeptiert.
• vollständig: für jedes (z, a) ist δ(z, a) definiert; sonst ergänzt man oft einen Fehlerzustand.

Beispielwörter

A101 und B011 sind gültige Eingabewörter; A001 wird wegen 00 verworfen, B10 ist zu kurz, und C101 ist wegen C kein Wort über Σ.

Bis hier stand die Sprachfrage im Mittelpunkt: Gehört dieses Eingabewort zur Sprache L(A)? DEA, NEA und Akzeptoren gehören zu dieser Sprachentscheidung: Am Ende wird akzeptiert oder verworfen. Mit dem Transduktor wechseln wir nicht nur die Darstellung, sondern das Modellziel. Ein Mealy-Automat modelliert, welche Ausgabe oder Reaktion ein System während der Verarbeitung erzeugt.

Q3.3 verfolgt anschließend eine andere Erweiterungsrichtung: Kellerautomaten ergänzen endliche Automaten um zusätzlichen Speicher durch einen Stack. Kurz gesagt: Mealy bedeutet endlicher Automat plus Ausgabe; Kellerautomat bedeutet endlicher Automat plus Stack.

Q3.1 hat gezeigt: Eine reguläre Grammatik erzeugt eine reguläre Sprache. Q3.2 ergänzt die erkennende Seite: Ein endlicher Automat erkennt eine reguläre Sprache. Reguläre Ausdrücke, reguläre Grammatiken und endliche Automaten beschreiben damit dieselbe Sprachklasse.

Formale Sprachen sind dabei Mengen von Wörtern über einem Alphabet, also Teilmengen von Σ*. Ein endlicher Automat wählt daraus genau die Eingabewörter aus, die nach vollständiger Verarbeitung akzeptiert werden.

Damit ist der Anschluss klar: Q3.2 fragt, wie ein Automat Eingabewörter einer Sprache erkennt. Q3.3 zeigt anschließend mit Kellerautomaten, wie ein zusätzlicher Speicher für kontextfreie und geschachtelte Strukturen genutzt wird.

Der DEA ist streng eindeutig: Zu Zustand und Eingabesymbol gibt es genau einen Folgezustand. Ein NEA lockert genau diese Stelle. Zu einem Zustand und Eingabesymbol kann es mehrere mögliche Folgezustände geben, manchmal zusätzlich ε-Übergänge ohne gelesenes Eingabesymbol.

Beim Lesen eines Eingabewortes entsteht deshalb nicht nur ein einzelner Weg, sondern eine Menge möglicher Pfade. Die Akzeptanzfrage lautet nicht mehr: Welcher eine Weg entsteht? Sondern: Gibt es mindestens einen Pfad, der nach vollständiger Verarbeitung in einem Endzustand endet?

• Determinismus: genau ein Folgezustand für jedes Paar aus Zustand und Eingabesymbol.
• Nichtdeterminismus: mehrere mögliche Folgezustände oder Pfade.
• Akzeptanz: Ein Eingabewort wird akzeptiert, wenn mindestens ein Pfad akzeptiert.
• ε-Übergang: Zustandswechsel ohne Verbrauch eines Eingabesymbols.

Didaktischer Merksatz: NEA sind oft kompakter in der Beschreibung, erkennen aber keine größere Sprachklasse als DEA. Beide Modelle erkennen reguläre Sprachen.