Endliche Automaten
Aus welchen Bestandteilen besteht ein endlicher erkennender Automat?
Erklärung: Das ist das ganze Modell — bewusst minimal. Jedes gelesene Zeichen löst genau einen Übergang aus; am Wortende entscheidet der erreichte Zustand über Akzeptieren oder Verwerfen.
Ein endlicher Automat merkt sich beim Lesen eines Wortes nur, in welchem Zustand er gerade ist — mehr Gedächtnis hat er nicht.
Erklärung: Richtig — der aktuelle Zustand IST das gesamte Gedächtnis. Alles, was der Automat wissen soll, muss in den Zuständen codiert sein.
Ein Automat über {0, 1} wechselt bei jeder gelesenen 1 zwischen den Zuständen GERADE und UNGERADE; im Startzustand GERADE liest er 1011. In welchem Zustand endet er?
Erklärung: Zeichen für Zeichen: 1 → UNGERADE, 0 → bleibt, 1 → GERADE, 1 → UNGERADE. Der Automat zählt die Einsen modulo 2 — genau das, was zwei Zustände speichern können.
Ein Automat betritt beim Lesen von abba zwischendurch zweimal einen akzeptierenden Zustand, steht nach dem letzten a aber in einem nicht-akzeptierenden Zustand. Akzeptiert er abba?
Erklärung: Akzeptiert wird ein Wort genau dann, wenn der Automat am WORTENDE in einem akzeptierenden Endzustand steht. Zwischendurch darf er akzeptierende Zustände betreten und wieder verlassen.
Die Menge aller Wörter, die ein erkennender Automat akzeptiert, heißt die vom Automaten erkannte ___.
Erklärung: Automat und Grammatik sind zwei Sichten auf dasselbe Objekt — die Grammatik erzeugt die Sprache, der Automat erkennt sie.
Im Zustandsdiagramm gehen vom Zustand Z0 zwei Pfeile mit demselben Zeichen a ab: einer nach Z1, einer nach Z2. Ist dieser Automat deterministisch?
Erklärung: Deterministisch heißt, dass für jeden Zustand und jedes Eingabezeichen GENAU EIN Folgezustand festgelegt ist — der Automat muss nie wählen. Endlich viele Zustände hat jeder endliche Automat; die Zahl der Endzustände ist egal.
Ein Drehkreuz hat die Zustände VERRIEGELT und OFFEN: Münze öffnet, Durchgehen verriegelt wieder. Was ist hier die „Eingabe" im Sinn des Automatenmodells?
Erklärung: Eingaben sind die Zeichen/Ereignisse, die Übergänge auslösen. Zustände beschreiben, WAS sich der Automat merkt; Eingaben, WAS passiert.
Ein endlicher Automat kann die Sprache „gleich viele a wie b, in beliebiger Länge" erkennen, wenn man ihm nur genügend Zustände gibt.
Erklärung: Falsch — für unbegrenztes Mitzählen bräuchte er unendlich viele Zustände. Jeder endliche Automat kann nur bis zu einer festen Grenze unterscheiden; genau hier endet die Kraft des Modells.
Ein Automat soll Wörter über {a, b} akzeptieren, die mit a beginnen. Was passiert sinnvollerweise, wenn das erste Zeichen ein b ist?
Erklärung: Ein Automat liest immer das ganze Wort. „Verwerfen" modelliert man als Fangzustand (Papierkorb-Zustand), der nie mehr verlassen wird.
Im Zustandsdiagramm wird der Automat gezeichnet: Kreise für die Zustände, beschriftete Pfeile für die ___.
Erklärung: Jeder Pfeil trägt das Eingabezeichen, das den Wechsel auslöst. Das Diagramm ist ein beschrifteter gerichteter Graph.
Ein Automat für PIN-Eingaben: Nach drei falschen Eingaben in Folge wechselt er in GESPERRT. Wie viele „Fehlversuche-Zustände" braucht er dafür mindestens (außer GESPERRT)?
Erklärung: Ein Automat hat keine Variablen — was er zählen soll, muss er in Zuständen ablegen. Begrenztes Zählen geht so; unbegrenztes nicht.
Derselbe Automat kann bei zweimaligem Lesen desselben Wortes zu unterschiedlichen Ergebnissen kommen, wenn er deterministisch ist.
Erklärung: Falsch — Determinismus heißt gerade, dass der Lauf durch Wort und Startzustand vollständig festgelegt ist. Gleiche Eingabe, gleicher Lauf, gleiches Ergebnis.
Welche Sprache erkennt dieser Automat über {a, b}? Start Z0; Z0 —a→ Z1; Z1 —b→ Z1; Z1 ist akzeptierend; alle anderen Übergänge führen in einen Fangzustand.
Erklärung: Vom Start führt nur a weiter; danach hält jedes b den Automaten im akzeptierenden Zustand. Akzeptiert werden a, ab, abb, abbb, …
FĂĽr welche dieser Aufgaben ist ein endlicher Automat das passende Modell?
Erklärung: Die Ampel ist Zustandsverhalten mit endlich vielen Fällen — genau das Automatenmodell. Unbegrenztes Klammern-Zählen übersteigt jede endliche Zustandsmenge, und Datenspeicherung ist gar kein Zustandsübergangs-Problem.