Zustandsautomat-Animator

Ein endlicher Automat hat ein festes Gedächtnis — seine Zustandsmenge. Egal wie lang die Eingabe ist, die Maschine verwendet nie mehr Speicher als ihre Anzahl an Zuständen. Deshalb können DFAs nicht unbegrenzt zählen: Es gibt keinen Zustand, der sich eine beliebige ganze Zahl „merkt“. Das Pumping-Lemma macht das präzise: Jeder hinreichend lange, von einem DFA akzeptierte String kann in einem mittleren Abschnitt beliebig oft wiederholt werden und wird trotzdem akzeptiert. Sprachen, die sich nicht pumpen lassen (wie aⁿbⁿ, gleiche Anzahl von a und b), benötigen einen Kellerautomaten oder eine Turingmaschine. Der Satz von Myhill-Nerode liefert das exakte Minimum: Die Anzahl der Zustände entspricht der Anzahl unterscheidbarer Äquivalenzklassen von Eingabepräfixen.

Ein deterministischer endlicher Automat ist einfach ein beschriftetes Diagramm aus Zuständen, die durch Pfeile verbunden sind. Für jeden Zustand und jedes Eingabesymbol gibt es genau einen Pfeil, dem man folgt — es gibt also nie eine Wahl. Der Automat liest die Zeichenkette einmal von links nach rechts und landet in einem einzigen Zustand. Ist dieser als akzeptierend markiert, gehört die Eingabe zur Sprache. Man verfolgt das, indem man ein Token entlang der Pfeile schiebt — genau das zeigt dieses Werkzeug.

Endliche Automaten stammen nicht aus der Informatik. 1943 beschrieben Warren McCulloch und Walter Pitts Neuronen als einfache An/Aus-Einheiten, die miteinander verdrahtet sind — das wurde zum ersten mathematischen Modell einer endlichen Zustandsmaschine. 1951 analysierte Stephen Kleene, welche Muster solche 'Nervennetze' erkennen können, und nannte sie reguläre Ereignisse — der Ursprung der heutigen regulären Ausdrücke. Der Automat, den du hier durchläufst, stammt also direkt aus dem Versuch zu erklären, wie das Gehirn rechnet.