Endliche Automaten

Lernziele

• Du kannst erklären, was ein endlicher Automat ist und woraus er besteht.
• Du kannst zu einem Zustandsdiagramm entscheiden, ob eine Eingabe akzeptiert wird.
• Du kannst selbst einen Automaten für eine einfache Aufgabe entwerfen.

Ein Türöffner als Automat

Stell dir eine Türe mit Drehkreuz vor, wie am Eingang eines Stadions. Das Drehkreuz kennt genau zwei Situationen: verriegelt und offen. Wirfst du eine Münze ein, wird es offen. Drückst du dagegen, ohne zu bezahlen, bleibt es verriegelt. Gehst du durch, verriegelt es sich wieder.

Das ist schon ein endlicher Automat. Er hat:

• Zustände: verriegelt, offen
• Eingaben: Münze, Drücken
• Übergänge: Regeln, welche Eingabe von welchem Zustand in welchen führt

Mehr braucht es nicht. Ein endlicher Automat ist eine Maschine mit einer endlichen Anzahl Zustände, die Eingaben liest und dabei den Zustand wechselt. Er hat kein Gedächtnis ausser dem Zustand, in dem er gerade steckt.

Automaten, die Wörter prüfen

In der Informatik füttern wir Automaten meistens mit Zeichenketten, z.B. aus den Zeichen 0 und 1. Der Automat liest die Kette Zeichen für Zeichen. Am Schluss schauen wir: Ist er in einem Endzustand gelandet? Dann sagen wir, er akzeptiert das Wort. Sonst nicht.

Hier ein Automat, der prüft, ob eine Kette eine gerade Anzahl Einsen enthält:

• Zustand G: bisher gerade Anzahl Einsen (Startzustand und Endzustand, markiert mit den Pfeilen von/zu dem Punkt)
• Zustand U: bisher ungerade Anzahl Einsen

Verfolge das Wort 1011 von Hand: Start in G → 1 → U → 0 → U → 1 → G → 1 → U. Ende in U, also nicht akzeptiert. Stimmt: 1011 hat drei Einsen.

Kurz überlegt

Die Übergangstabelle

Statt eines Diagramms kann man denselben Automaten als Tabelle aufschreiben. Das ist die Form, die ein Programm direkt verarbeiten kann:

Diagramm und Tabelle sind zwei Darstellungen von genau derselben Sache. Beim Entwerfen hilft das Diagramm, beim Programmieren die Tabelle.

Ein Automat in Python

Ein endlicher Automat ist so einfach, dass er in ein paar Zeilen Python passt. Die Übergangstabelle wird zu einem Dictionary:

uebergang = {
    ("G", "0"): "G",
    ("G", "1"): "U",
    ("U", "0"): "U",
    ("U", "1"): "G",
}

def akzeptiert(wort):
    zustand = "G"
    for zeichen in wort:
        zustand = uebergang[(zustand, zeichen)]
    return zustand == "G"

print(akzeptiert("1011"))
print(akzeptiert("110"))

Führe das Programm aus und vergleiche mit deiner Handrechnung von oben.

Aufgabe: Automat für «endet auf 1»

Entwirf einen Automaten mit zwei Zuständen, der genau die Wörter akzeptiert, die auf 1 enden. Zeichne zuerst das Zustandsdiagramm auf Papier, dann passe das Python-Programm an: Ändere die Übergangstabelle und den Endzustand.

uebergang = {
    # ("Zustand", "Zeichen"): "Folgezustand"
}

def akzeptiert(wort):
    zustand = "A"  # Startzustand, passe an
    for zeichen in wort:
        zustand = uebergang[(zustand, zeichen)]
    return zustand == "A"  # Endzustand, passe an

print(akzeptiert("01"))   # sollte True sein
print(akzeptiert("10"))   # sollte False sein
print(akzeptiert(""))     # sollte False sein

Merke

Ein endlicher Automat (auch DEA, deterministischer endlicher Automat) besteht aus Zuständen, einem Startzustand, Endzuständen und einer Übergangsfunktion. Er akzeptiert ein Wort, wenn er nach dem Lesen aller Zeichen in einem Endzustand steht. «Deterministisch» heisst: Für jeden Zustand und jedes Zeichen gibt es genau einen Folgezustand — der Automat hat nie eine Wahl.