Endliche Automaten

Aus welchen Bestandteilen besteht ein endlicher erkennender Automat?

• ● Zustände, Übergänge mit Eingabezeichen, ein Startzustand und akzeptierende Endzustände
• ○ Variablen, Schleifen und Funktionen
• ○ Tabellen, Schlüssel und Abfragen

Ein endlicher Automat merkt sich beim Lesen eines Wortes nur, in welchem Zustand er gerade ist — mehr Gedächtnis hat er nicht.

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?

• ● Nein — es zählt nur der Zustand nach dem letzten Zeichen
• ○ Ja — er hat einen akzeptierenden Zustand berührt
• ○ Ja — er konnte das ganze Wort ohne Abbruch lesen

Die Menge aller Wörter, die ein erkennender Automat akzeptiert, heißt die vom Automaten erkannte ___.

Im Zustandsdiagramm gehen vom Zustand Z0 zwei Pfeile mit demselben Zeichen a ab: einer nach Z1, einer nach Z2. Ist dieser Automat deterministisch?

• ● Nein — für Z0 und a ist der Folgezustand nicht eindeutig festgelegt
• ○ Ja — er hat nur endlich viele Zustände
• ○ Ja — solange er genau einen Endzustand hat

Ein Drehkreuz hat die Zustände VERRIEGELT und OFFEN: Münze öffnet, Durchgehen verriegelt wieder. Was ist hier die „Eingabe" im Sinn des Automatenmodells?

• ● Die Ereignisse Münze und Durchgehen
• ○ Die Anzahl der wartenden Personen
• ○ Die beiden Zustände selbst

Im Zustandsdiagramm wird der Automat gezeichnet: Kreise für die Zustände, beschriftete Pfeile für die ___.

Derselbe Automat kann bei zweimaligem Lesen desselben Wortes zu unterschiedlichen Ergebnissen kommen, wenn er deterministisch ist.

Für welche dieser Aufgaben ist ein endlicher Automat das passende Modell?

• ● die Steuerung einer Ampel mit den Phasen Rot, Rot-Gelb, Grün und Gelb
• ○ das Mitzählen beliebig vieler geöffneter Klammern in einem Programmtext
• ○ das Speichern aller Kundendaten eines Online-Shops

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?

• ● UNGERADE — das Wort enthält drei Einsen
• ○ GERADE — das Wort hat vier Zeichen
• ○ Im Startzustand, weil das Wort mit 1 beginnt

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.

Ein Automat soll Wörter über {a, b} akzeptieren, die mit a beginnen. Was passiert sinnvollerweise, wenn das erste Zeichen ein b ist?

• ● Er wechselt in einen Fangzustand, aus dem kein akzeptierender Zustand mehr erreichbar ist
• ○ Er ignoriert das b und wartet auf ein a
• ○ Er bricht mit einer Fehlermeldung ab

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)?

• ● 3 — für null, einen und zwei Fehlversuche
• ○ 1 — er zählt die Fehlversuche in einer Variablen
• ○ Keinen — das erledigt der Endzustand

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.

• ● Ein a, gefolgt von beliebig vielen b
• ○ Beliebig viele a, dann genau ein b
• ○ Alle Wörter, die ein a enthalten