Grenzen endlicher Automaten

Lernziele

• Du kannst Automaten für verschiedene Sprachen entwerfen.
• Du kannst begründen, warum ein endlicher Automat manche Aufgaben nicht lösen kann.

Entwerfen üben

Beim Entwerfen eines Automaten ist die wichtigste Frage: Was muss sich der Automat merken? Jede Antwort auf diese Frage wird ein Zustand.

Beispiel: «Akzeptiere alle Wörter, die 00 enthalten.» Was muss man sich beim Lesen merken?

1. «Bisher nichts Besonderes gesehen» → Zustand A
2. «Das letzte Zeichen war eine 0» → Zustand B
3. «Ich habe schon 00 gesehen, fertig» → Zustand C (Endzustand)

Sobald der Automat in C ist, bleibt er dort — egal was noch kommt. 00 wurde ja bereits gefunden.

Aufgabe 1: Von Hand entwerfen

Zeichne für jede dieser Sprachen ein Zustandsdiagramm auf Papier:a) Alle Wörter mit mindestens drei Zeichen.b) Alle Wörter, die mit 1 beginnen und auf 0 enden.c) Alle Wörter, in denen nie zwei Einsen nebeneinander stehen.

Aufgabe 2: In Python umsetzen

Setze deinen Automaten aus Aufgabe 1 b) um: Wörter, die mit 1 beginnen und auf 0 enden. Du brauchst einen zusätzlichen «Fehlerzustand» für Wörter, die mit 0 beginnen — aus dem kommt der Automat nie mehr heraus.

uebergang = {
    # ergänze die Tabelle
}

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

print(akzeptiert("10"))     # True
print(akzeptiert("1110"))   # True
print(akzeptiert("01"))     # False

Was ein Automat nicht kann

Jetzt eine Sprache, die harmlos aussieht: alle Wörter der Form 01, 0011, 000111, … — also erst n Nullen, dann genau gleich viele Einsen.

Versuch, dir einen Automaten dafür vorzustellen. Was müsste er sich merken? Die Anzahl der gelesenen Nullen. Aber die kann beliebig gross werden: 5, 100, eine Million. Ein endlicher Automat hat nur endlich viele Zustände — er kann sich nicht beliebig viele verschiedene Anzahlen merken. Irgendwann muss er zwei verschiedene Anzahlen im selben Zustand landen lassen, und dann kann er sie nicht mehr unterscheiden.

Das Kernproblem

Ein endlicher Automat kann nicht zählen. Alles, was unbeschränktes Zählen oder Mitschreiben braucht, liegt ausserhalb seiner Möglichkeiten. Dazu gehört auch das Prüfen, ob in einem Text alle Klammern korrekt geschlossen sind — etwas, das jeder Programm-Editor können muss.

Verstanden?

Für solche Aufgaben braucht es eine stärkere Maschine. Die schauen wir uns auf der nächsten Seite an.