Endliche Automaten in Python

1. Einrichten

Lege im Terminal (StrgJ) einen Ordner an und öffne ihn mit StrgK StrgO:

mkdir /workspace/automata

Alle Dateien dieser Aktivität kommen in diesen Ordner. Ein Programm startest du im Terminal mit python3 und dem Namen der Datei.

2. Ein Drehkreuz

Das Drehkreuz am Eingang zum Schwimmbad ist erst zu. Wirfst du eine Münze ein, ist es offen; gehst du durch (»drücken«), ist es wieder zu. Drückst du, ohne zu zahlen, bleibt es zu, und eine zweite Münze in ein offenes Drehkreuz ist verschenkt. Als Bild, mit einem Kreis für jeden Zustand und einem Pfeil für jeden Übergang:

Lege turnstile.py an:

# Ein Drehkreuz wie am Eingang zum Schwimmbad. Für jeden Zustand und jede
# Eingabe steht hier, in welchen Zustand das Drehkreuz wechselt.
TRANSITIONS = {
    ('zu', 'münze'): 'offen',
    ('zu', 'drücken'): 'zu',
    ('offen', 'münze'): 'offen',
    ('offen', 'drücken'): 'zu',
}


def run(inputs):
    state = 'zu'
    for symbol in inputs:
        new_state = TRANSITIONS[(state, symbol)]
        print(f'{state:>5}  {symbol:<8} → {new_state}')
        state = new_state
    return state


run(['drücken', 'münze', 'drücken', 'drücken'])

TRANSITIONS ist die Tabelle des Automaten: Zu jedem Paar aus Zustand und Eingabe steht dort der neue Zustand, so wie zu jedem Pfeil im Bild. TRANSITIONS[('zu', 'münze')] ist 'offen'. Die Funktion run beginnt in zu, liest die Eingaben der Reihe nach, schlägt für jede den neuen Zustand nach und gibt ihn aus. Starte das Programm:

python3 turnstile.py

Jede Zeile ist ein Pfeil im Bild: der alte Zustand, die Eingabe und der neue Zustand. Probier eigene Folgen aus, indem du die letzte Zeile änderst. Was passiert, wenn du run(['tritt']) schreibst?

3. Ein Automat, der rechnen kann

Das Drehkreuz macht etwas. Viele Automaten beantworten stattdessen eine Frage über ein Wort: Gehört es dazu oder nicht? Sie haben dafür einen Startzustand und einen oder mehrere akzeptierende Zustände, im Bild mit doppeltem Rand. Der Automat liest das Wort; endet er in einem akzeptierenden Zustand, nimmt er das Wort an.

Hier ist ein Automat, der Binärzahlen liest und annimmt, wenn sie durch 3 teilbar sind:

Wie kann er das, ohne zu rechnen? Sein Zustand ist der Rest, der bisher beim Teilen durch 3 bleibt. Liest er von links eine weitere Ziffer, verdoppelt sich die Zahl, und die Ziffer kommt dazu: Aus 11 (3) wird mit einer 0 die 110 (6), mit einer 1 die 111 (7). Mit dem Rest passiert dasselbe: Aus Rest r wird mit der Ziffer d der Rest von 2 · r + d. Mehr als den Rest muss sich der Automat nicht merken. Für 110:

Er endet in 0, also ist 6 durch 3 teilbar. Lege divisible.py an:

# Ist eine Binärzahl durch 3 teilbar? Der Automat liest sie Ziffer für Ziffer
# von links. Sein Zustand ist der Rest, der bis dahin beim Teilen durch 3 bleibt.
START = 0
ACCEPTING = {0}
TRANSITIONS = {
    (0, '0'): 0, (0, '1'): 1,
    (1, '0'): 2, (1, '1'): 0,
    (2, '0'): 1, (2, '1'): 2,
}


def accepts(word):
    state = START
    for symbol in word:
        state = TRANSITIONS[(state, symbol)]
    return state in ACCEPTING


for word in ['11', '110', '111', '1001', '10000']:
    print(word, int(word, 2), accepts(word))

START und ACCEPTING sind neu: Die Funktion accepts beginnt in START und sagt am Ende, ob der letzte Zustand in der Menge ACCEPTING liegt. Zum Vergleich gibt das Programm neben jedem Wort seinen Wert aus; int(word, 2) liest eine Binärzahl.

python3 divisible.py

Der Automat hat nur drei Zustände und liest jede Ziffer genau einmal. Darum ist ihm egal, wie lang die Zahl ist. bin(3 ** 1000) schreibt 3 hoch 1000 als Binärzahl, mit 0b davor, das [2:] abschneidet. Hänge diese Zeile an und probier es aus:

print(accepts(bin(3 ** 1000)[2:]))

Das sind 1585 Ziffern, und accepts merkt sich nie mehr als eine Zahl von 0 bis 2.

Was ein Automat nicht kann

Die Stärke des Automaten ist auch seine Grenze: Er weiß nur, in welchem Zustand er ist, und davon hat er endlich viele. Was er sich merken müsste, ohne dass es eine feste Obergrenze gibt, kann er nicht. Darum heißen diese Automaten endlich.

4. Das Zahlenschloss

Am Fahrradkeller hängt ein Zahlenschloss mit Tastenfeld. Es hat keine Enter-Taste: Es geht auf, sobald die letzten vier getippten Ziffern der Code sind, 1213. Als Automat merkt es sich, wie viel vom Code schon stimmt; darum heißen seine Zustände so, wie das, was vom Code schon getippt ist:

# Ein Zahlenschloss mit dem Code 1213. Es öffnet, sobald die letzten vier
# getippten Ziffern der Code sind. Der Zustand merkt sich, wie viel vom Code
# schon stimmt.
START = 'start'
ACCEPTING = {'1213'}
TRANSITIONS = {
    ('start', '1'): '1',
    ('1', '2'): '12',
    ('12', '1'): '121',
    ('121', '3'): '1213',
}


def opens(digits):
    state = START
    for digit in digits:
        # Fehlt ein Übergang, geht es zurück zum Start.
        state = TRANSITIONS.get((state, digit), START)
    return state in ACCEPTING


for digits in ['1213', '991213', '12', '121213']:
    print(digits, opens(digits))

Neu ist TRANSITIONS.get((state, digit), START): get sucht den Übergang in der Tabelle, und gibt es ihn nicht, nimmt es START. So muss nicht jede der zehn Ziffern in jedem Zustand einzeln in der Tabelle stehen; alles, was nicht zum Code passt, führt zurück zum Anfang. Starte das Programm:

Die ersten drei Zeilen stimmen. Aber die letzte: Lena hat sich vertippt, 1 2 1 2, und dann richtig weitergetippt, 1 3. Die letzten vier Ziffern sind 1213, und trotzdem bleibt das Schloss zu. Geh die Ziffern mit dem Automaten durch: Nach 121 kommt eine 2. Das ist nicht die erwartete 3, also geht es zurück nach start. Dabei hat Lena mit 12 gerade wieder den Anfang des Codes getippt. Der Automat hat es vergessen.

Automatron zeichnet nach

Für jede Ziffer in jedem Zustand die richtige Antwort zu finden, ist Denkarbeit. Ein Werkzeug kann sie dir abnehmen: Automatron baut aus einem regulären Ausdruck einen Automaten. (0|1|2|3|4|5|6|7|8|9)*1213 heißt: beliebig viele Ziffern (| ist »oder«, * »beliebig oft, auch keinmal«), danach 1213. Gib den Ausdruck in Automatron ein. Ganz unten auf der Seite zeigt es den kleinsten Automaten, der dasselbe tut:

s0 ist start, s1 ist 1, s2 ist 12, s3 ist 121 und s4 ist 1213. Vergleiche die Pfeile mit deiner Tabelle: Automatron zeichnet auch die Pfeile zurück nach s0, die in lock.py das get erledigt. Darüber steht, wie Automatron zu diesem Automaten gekommen ist. Einen Teil davon baust du gleich selbst.

5. Ein Automat, der rät

Beim Schloss steckte die Arbeit in den Pfeilen zurück. Es geht auch anders, wenn der Automat raten darf: In start wartet er. Kommt eine 1, könnte hier der Code anfangen, oder auch nicht. Der Automat nimmt einfach beides: Er bleibt in start und geht zugleich nach 1. Ab da folgt er dem Code; passt eine Ziffer nicht, endet dieser Weg einfach.

So ein Automat heißt nichtdeterministischer endlicher Automat, kurz NEA. Die Automaten von vorhin, bei denen jeder Schritt feststeht, heißen deterministisch, kurz DEA. Ein NEA nimmt ein Wort an, wenn wenigstens einer seiner Wege in einem akzeptierenden Zustand endet.

Python kann nicht raten, aber es kann alle Wege zugleich verfolgen: Statt eines Zustands merkt sich opens eine Menge von Zuständen, nämlich alle, in denen der NEA gerade sein könnte. Die Tabelle führt darum zu Mengen. Lege lock_nfa.py an:

# Das Zahlenschloss als nichtdeterministischer endlicher Automat (NEA).
# Ein Übergang führt hier zu einer Menge von Zuständen: Der NEA darf raten.
DIGITS = '0123456789'
START = 'start'
ACCEPTING = {'1213'}
TRANSITIONS = {}

# In start wartet der NEA: Jede Ziffer führt wieder nach start …
for digit in DIGITS:
    TRANSITIONS[('start', digit)] = {'start'}
# … aber bei einer 1 darf er auch raten, dass hier der Code beginnt.
TRANSITIONS[('start', '1')] = {'start', '1'}
TRANSITIONS[('1', '2')] = {'12'}
TRANSITIONS[('12', '1')] = {'121'}
TRANSITIONS[('121', '3')] = {'1213'}


def opens(digits):
    states = {START}
    for digit in digits:
        new_states = set()
        for state in states:
            new_states |= TRANSITIONS.get((state, digit), set())
        states = new_states
        print(digit, sorted(states))
    return len(states & ACCEPTING) > 0


if __name__ == '__main__':
    print(opens('121213'))

Ein paar Zeichen sind neu. {'start', '1'} ist eine Menge; a |= b fügt alle Elemente von b zur Menge a hinzu, und states & ACCEPTING sind die Zustände, die in beiden Mengen liegen. Der Teil unter if __name__ == '__main__': läuft nur, wenn du die Datei selbst startest, nicht, wenn ein anderes Programm sie lädt; das brauchst du gleich.

python3 lock_nfa.py

Nach jeder Ziffer steht die Menge der Zustände, in denen der NEA sein könnte. 121213 öffnet, ohne dass du über einen einzigen Pfeil zurück nachdenken musstest.

6. Vom NEA zum DEA

Ein NEA ist leicht zu schreiben. Ein DEA ist leichter auszuführen: ein Nachschlagen pro Zeichen, kein Hantieren mit Mengen, und genau so bauen ihn Programme in Hardware oder in schnelle Suchfunktionen ein. Zum Glück muss man sich nicht entscheiden. Die Mengen, die opens ausgibt, sind selbst die Zustände eines DEA. Ein Programm kann sie alle aufzählen, ausgehend von {start}: Für jede Menge und jede Ziffer rechnet es aus, welche Menge danach kommt, und macht weiter, bis keine neue mehr auftaucht. Das heißt Potenzmengenkonstruktion. Lege convert.py an:

# Die Potenzmengenkonstruktion: Sie baut aus einem NEA einen DEA. Jeder
# Zustand des DEA ist eine Menge von Zuständen des NEA, nämlich die, in denen
# der NEA gerade sein könnte.
from lock_nfa import DIGITS, START, ACCEPTING, TRANSITIONS


# Alle Zustände, in die der NEA aus states mit symbol kommt.
def step(states, symbol):
    new_states = set()
    for state in states:
        new_states |= TRANSITIONS.get((state, symbol), set())
    return frozenset(new_states)


def to_dfa():
    start = frozenset({START})
    found = {start}
    todo = [start]
    transitions = {}
    while todo:
        states = todo.pop()
        for symbol in DIGITS:
            target = step(states, symbol)
            transitions[(states, symbol)] = target
            if target not in found:
                found.add(target)
                todo.append(target)
    return found, transitions


found, transitions = to_dfa()
print(len(found), 'Zustände')
for (states, symbol), target in transitions.items():
    if target != {START}:
        print(sorted(states), symbol, '→', sorted(target))

frozenset ist eine Menge, die sich nicht mehr ändern lässt. Nur solche Mengen dürfen in Python Schlüssel eines dict sein oder in einer anderen Menge liegen. todo ist die Liste der Mengen, deren Übergänge noch nicht ausgerechnet sind. Am Ende gibt das Programm aus, wie viele Zustände der DEA hat, und alle Übergänge, die nicht zurück nach {start} führen:

Fünf Zustände, wie bei Automatron. Und sieh dir die Übergänge an: ['1', '121', 'start'] 2 → ['12', 'start'] ist genau der Pfeil, den du in lock.py von Hand gesucht hast, von 121 mit einer 2 nach 12. Das Programm hat ihn gefunden, ohne nachzudenken.

Ein Generalschlüssel

Jetzt zeigt sich, wie viel leichter ein NEA zu ändern ist.

Starte danach convert.py noch einmal. Es baut den DEA aus deinem neuen NEA, ohne dass du daran etwas ändern musst. Den DEA mit Generalschlüssel von Hand zu bauen, mit allen Pfeilen zurück, wäre eine knifflige Aufgabe; Automatron kommt mit (0|1|2|3|4|5|6|7|8|9)*(1213|4711) auf dasselbe Ergebnis.

Wenn der DEA explodiert

Beim Schloss hat der DEA so viele Zustände wie der NEA. Das ist nicht immer so. Ein NEA, der prüft, ob die N-te Ziffer von hinten eine 1 ist, rät, wo diese 1 steht, und zählt dann bis zum Ende ab. Er braucht N + 1 Zustände. Lege last.py an:

# Ist die N-te Ziffer von hinten eine 1? Der NEA rät, wo diese 1 steht, und
# zählt danach die Ziffern bis zum Ende ab.
N = 3
DIGITS = '01'
START = 0
ACCEPTING = {N}
TRANSITIONS = {
    (0, '0'): {0},
    (0, '1'): {0, 1},
}
for i in range(1, N):
    TRANSITIONS[(i, '0')] = {i + 1}
    TRANSITIONS[(i, '1')] = {i + 1}

Ändere in convert.py die Zeile from lock_nfa import … zu from last import … und starte es. Ändere dann N in last.py auf 5 und starte convert.py noch einmal.

Der DEA kann nicht raten, wo die 1 steht. Er muss sich darum alle letzten N Ziffern merken, und jede Möglichkeit ist ein eigener Zustand. Bei N = 30 wären das über eine Milliarde. Automatron zeigt unter den Beispielen den DEA für »drittletztes Symbol ist 1«; zähl seine Zustände.

7. Zusammenfassung

• Ein endlicher Automat hat endlich viele Zustände und eine Tabelle, die für jeden Zustand und jedes Zeichen den nächsten nennt. In Python ist das ein dict mit Paaren als Schlüsseln.
• Ein Automat, der Wörter prüft, hat einen Startzustand und akzeptierende Zustände. Er nimmt ein Wort an, wenn er am Ende in einem akzeptierenden Zustand ist.
• Ein DEA weiß bei jedem Zeichen genau, wohin. Ein NEA darf mehrere Wege zugleich gehen; er nimmt ein Wort an, wenn einer davon akzeptiert. Verfolgt wird er mit einer Menge von Zuständen.
• Die Potenzmengenkonstruktion macht aus jedem NEA einen DEA, der dasselbe tut. Er kann aber exponentiell mehr Zustände haben.
• Was keine feste Obergrenze hat, etwa gleich viele a wie b, kann kein endlicher Automat prüfen.

8. Wie geht es weiter?

• Reguläre Ausdrücke in Python. import re und re.fullmatch('[0-9]*1213', '121213') prüfen dasselbe wie dein Schloss. Hinter re steckt die Idee dieser Seite: Ausdruck, Automat, Zeichen für Zeichen lesen.
• Automatron ganz. Automatron macht mehr als die Potenzmengenkonstruktion: Erst baut es aus dem Ausdruck einen NEA mit ε-Übergängen (Thompson-Konstruktion), am Ende verkleinert es den DEA (Minimierung). Probier die Beispiele aus und lies die Erklärungen zwischen den Bildern.
• Mehr als endlich. Klammern prüfen, ob jede ( ein ) hat, kann ein endlicher Automat nicht. Ein Kellerautomat kann es, mit einem Stapel als Gedächtnis. So prüfen Compiler deinen Code.