Endliche Automaten einfach erklärt

Genau drei Euro am Getränkeautomaten

Ein endlicher Automat ist die einfachste Rechenmaschine: Er liest ein Wort Zeichen für Zeichen und sagt am Ende „ja“ oder „nein“. Mit ihm lässt sich zum Beispiel prüfen, ob ein Getränkeautomat in der Mensa genau drei Euro bekommen hat.

Der Automat merkt sich nur eines: wie viel schon eingeworfen wurde. Das reicht für diese Aufgabe. Es zeigt auch, was eine Maschine mit so wenig Gedächtnis kann und was nicht.

Am Ende dieser Lektion

Notiz

Ich kann einen endlichen Automaten Zeichen für Zeichen verfolgen und sagen, welche Wörter er akzeptiert.

Schlüsselwörter

Begriff	Was er bedeutet	Beispiel
Zustand	das, woran sich der Automat gerade erinnert	s1
Übergang	die Regel, in welchen Zustand ein gelesenes Zeichen führt
Startzustand	der Zustand, in dem jeder Lauf beginnt
Akzeptierender Zustand	ein Zustand, in dem „ja“ gilt, wenn das Wort endet
Eingabewort	die Zeichenfolge, die der Automat liest	12
Sprache	die Menge aller Wörter, die ein Automat akzeptiert

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Ein Automat besteht aus Zuständen und Übergängen

Ein Zustand ist das, woran sich der Automat gerade erinnert. Beim Getränkeautomaten ist das der Betrag, der schon im Schlitz liegt: 0, 1, 2 oder 3 Euro.

Jedes gelesene Zeichen löst einen Übergang aus. Bei „1 Euro“ im Zustand 0 Euro geht es zu 1 Euro. Der Startzustand ist 0 Euro. Der akzeptierende Zustand ist 3 Euro.

Dieselben Regeln als Tabelle

Zustand	Münze 1 Euro	Münze 2 Euro
0 Euro (Start)	1 Euro	2 Euro
1 Euro	2 Euro	3 Euro
2 Euro	3 Euro	keine Regel: abgelehnt
3 Euro (akzeptiert)	keine Regel: abgelehnt	keine Regel: abgelehnt

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Ein Wort wird Zeichen für Zeichen verfolgt

Zum Verfolgen beginnen Sie im Startzustand. Für jedes Zeichen suchen Sie die Regel und gehen in den neuen Zustand.

Wenn das Wort zu Ende ist, sehen Sie nach, wo Sie stehen. Ein akzeptierender Zustand heißt „ja“, jeder andere „nein“. Fehlt unterwegs eine Regel, bleibt der Automat stehen und lehnt das Wort ab.

Zwei Wörter im Vergleich

Wort	Schritte	Endzustand	Ergebnis
12	0 Euro, dann 1 Euro, dann 3 Euro	3 Euro	ja
22	0 Euro, dann 2 Euro, dann keine Regel	abgebrochen	nein
1	0 Euro, dann 1 Euro	1 Euro	nein, zu wenig
121	0 Euro, 1 Euro, 3 Euro, dann keine Regel	abgebrochen	nein, zu viel

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Der Automat als Python-Programm

Code: python

# Ein Getraenkeautomat nimmt 1- und 2-Euro-Muenzen. Er will genau 3 Euro.
regeln = {
    "s0,1": "s1", "s0,2": "s2",
    "s1,1": "s2", "s1,2": "s3",
    "s2,1": "s3",
}
wort = "12"
zustand = "s0"
for muenze in wort:
    schluessel = zustand + "," + muenze
    if schluessel not in regeln:
        zustand = "FEHLER"
        break
    zustand = regeln[schluessel]
    print("Muenze", muenze, "-> Zustand", zustand)
print("Akzeptiert:", zustand == "s3")
# Aendern Sie wort in "21", "111" und "22" und fuehren Sie jedes Mal aus.

Ein häufiger Fehler

Warnung

Viele denken, ein Automat sagt „ja“, sobald er einmal einen akzeptierenden Zustand berührt. Das stimmt nicht. Es zählt nur der Zustand nach dem letzten Zeichen. Das Wort 121 berührt 3 Euro, endet aber im Nichts und wird abgelehnt.

Auch ein Lexer ist ein Automat

Echte Software nutzt Automaten oft. Der Lexer eines Compilers erkennt Zahlen, Namen und Zeichen mit Automaten. Das Werkzeug flex schreibt ihn aus Mustern und macht daraus Tabellen mit Zuständen.

Die Befehle zeigen zwei kleine Beispiele. Das erste zählt Einsen mit einem Automaten aus nur zwei Zuständen. Das zweite ist der Rechner calc, der 007 als eine einzige Zahl liest.