Zustandsautomat-Animator

DFA-Übergänge live im Zustandsdiagramm verfolgen

Rechenbeispiel — Zustandsautomat-Animator

Nächstes Symbol	'1'

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

endliches Gedächtnis, unendliche Strings 🖖

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 Token, ein Pfad 🖖

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.

aus einem Modell von Neuronen entstanden 🖖

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.

Aufgabe vollständig gelöst

Warum kein endlicher Automat 0en und 1en abgleichen kann, egal wie viele Zustände man ihm gibt 8 Schritte
Der Paritätsautomat auf dieser Seite hat zwei Zustände und liest 101101, sechs Symbole, ohne jemals einen dritten zu benötigen. Übergeben Sie ihm sechs Millionen Symbole, benötigt er immer noch zwei. Was also kann ein Automat mit einer festen Anzahl von Zuständen nicht? Und wie beweist man, dass ein Automat nicht existiert, statt lediglich daran zu scheitern, einen zu finden?
1. Beobachten Sie den vorhandenen Automaten. Die Parität beginnt in e, und jede 1 wechselt sie. Sechs Symbole später ist er wieder in e und die Eingabe wird akzeptiert. Unterwegs hat sich nichts angesammelt: Der Automat befindet sich beim sechsten Symbol in genau demselben Zustand, in dem er sich auch beim ersten Symbol hätte befinden können.
  
  $e 1 o 0 o 1 e 1 o 0 o 1 e$
2. Das ist die gesamte Ressource. Das Gedächtnis eines DFA ist der Zustand, in dem er sich befindet, und sonst nichts. Kein Zähler, kein Stapel, kein Band, auf das er schreiben könnte. Nach dem Lesen eines beliebigen Präfix ist alles, was der Automat über dieses Präfix weiß, welchen seiner k Zustände er nun einnimmt.
  
  $∣ Q ∣ = k ⟹ at most k distinguishable pasts$
3. Suchen Sie also nach etwas, das offensichtlich mehr erfordert. Betrachten Sie die Zeichenketten, die aus einer Anzahl von Nullen bestehen, gefolgt von genau ebenso vielen Einsen. 01 ist eine solche, 0011 ist eine, 001 ist keine und 0110 ebenfalls nicht.
  
  $L = {0^{n} 1^{n} : n \geq 0}$
4. Nehmen wir an, ein DFA mit k Zuständen akzeptiert diese Sprache. Fragen Sie nicht, wie der Automat aussieht — das wird Ihnen nie mitgeteilt werden. Speisen Sie ihn einfach mit den k+1 Präfixen aus 0 bis k Nullen und notieren Sie, in welchem Zustand er jeweils endet.
  
  $0^{0}, 0^{1}, \dots, 0^{k} ⟶ k + 1 strings into k states$
5. Schubfachprinzip. Es gibt mehr Präfixe als Zustände, also landen zwei von ihnen an demselben Ort. Nennen wir sie 0ⁱ und 0ʲ mit i kleiner als j. Von diesem Moment an kann der Automat sie nicht mehr unterscheiden, und zwar nicht, weil er schlecht konstruiert wäre. Der Zustand ist alles, was er hat, und die beiden Zeichenketten haben ihn in denselben versetzt.
  
  $δ^{*} (q_{0}, 0^{i}) = δ^{*} (q_{0}, 0^{j}), i < j \leq k$
6. Fügen Sie nun beiden Fortsetzungen dasselbe hinzu: i Einsen. Derselbe Startzustand, dieselben Symbole, also derselbe Endzustand und somit dasselbe Ergebnis. Es gibt für den Automaten keinen Spielraum, etwas anderes zu tun.
  
  $δ^{*} (q_{0}, 0^{i} 1^{i}) = δ^{*} (q_{0}, 0^{j} 1^{i})$
7. Und die beiden Ergebnisse müssen unterschiedlich sein. 0ⁱ1ⁱ hat übereinstimmende Anzahlen und gehört dazu; 0ʲ1ⁱ tut dies nicht, weil j ungleich i ist. Das eine muss akzeptiert und das andere abgelehnt werden, aber der Automat gibt ihnen dieselbe Antwort. Was zusammenbricht, ist die Annahme, dass er existierte.
  
  $0^{i} 1^{i} \in L, 0^{j} 1^{i} \in / L$
8. Gehen Sie das Argument noch einmal durch und achten Sie darauf, was darin nie aufgetaucht ist: ein Wert für k. Zwei, die eigene Größe des Paritätsautomaten, oder zwei Milliarden: k+1 Präfixe sind so oder so zahlreicher als k Zustände. Setzt man jedoch eine Obergrenze für n, wird die Sprache sofort regulär: Das Abgleichen bis zu N benötigt 2N+2 Zustände, also 22 für N = 10 und 202 für N = 100.
  
  ${0^{n} 1^{n} : n \leq N} needs 2 N + 2 states$
Antwort

Kein endlicher Automat akzeptiert sie, ungeachtet seiner Größe. Der Beweis benötigt keinerlei Wissen darüber, wie der Automat aufgebaut ist, sondern nur, dass k+1 Dinge nicht an k Orten Platz finden, ohne dass sich zwei davon einen Ort teilen, und dass das Teilen eines Zustands ein Vergessen bedeutet. Der Paritätsautomat zeigt dasselbe im Kleinformat: Speisen Sie ihn mit 0, dann mit 00, dann mit 000, und alle drei belassen ihn in e, weil er sich Nullen überhaupt nicht ansieht.

In der Obergrenze liegt die gesamte Schwierigkeit. Das Abgleichen bis zu N ist einfach, mit 2N+2 Zuständen — ein weiteres Paar für jedes Symbol, das Sie erreichen wollen — und diese Anzahl wächst ohne Ende, sodass für jedes konkrete N ein Automat existiert, aber kein Automat jedes N abdeckt. Diese Lücke ist es, was „endlicher Speicher“ bedeutet, und deshalb ist der nächste Schritt nach einem DFA dadurch definiert, dass man ihm einen Stapel gibt: einen unbeschränkten Speicher, der genau deshalb wieder hinzugefügt wird, weil sein Fehlen dies kostet.

Quellen (2)

Insight block 3 — the nerve-net model the finite automaton descends from: W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity." Bulletin of Mathematical Biophysics 5(4), 115–133, 1943.
Insight block 1 — the theorem that fixes the minimum state count: A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4), 541–544, 1958.

Vom 42Math-Team · Aktualisiert 2026-06-03

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

endet mit 01 - Der Suffix-Erkenner akzeptiert Zeichenketten, die auf 01 enden.
abgelehnt (endet auf 10) - Geh bis zum Ende. Die Maschine endet in q1 und lehnt ab, obwohl sie sich zwischendurch im akzeptierenden Zustand q2 befand. Irgendwo in der Mitte eine 01 zu lesen, ist eben nicht dasselbe, wie auch mit ihr zu enden. Die gesamte Antwort eines DFA besteht ausschließlich aus dem Zustand nach dem allerletzten Symbol. Er besitzt keinerlei Gedächtnis dafür, dass er zuvor jemals an einem besseren Punkt war.
gerade Anzahl Einsen ✓ - Der Paritätsautomat akzeptiert Binärstrings mit einer geraden Anzahl an Einsen.
ungerade Anzahl Einsen ✗ - Drei 1en in der Eingabe, und der Paritätsautomat springt bei jeder von ihnen um: e, o, o, e, o. Er endet in o und lehnt ab. Hier wird rein gar nichts gezählt. Zwei Zustände sind alles, was er besitzt, und auch alles, was er braucht. Ob die bisherige Anzahl ungerade ist, ist nämlich die einzige Tatsache, die es sich bei einer Zeichenkette beliebiger Länge zu merken lohnt.
enthält 101 ✓ - Die Maschine erreicht s3 beim vierten Symbol und kann ihn dann nicht mehr verlassen: s3 geht bei einer 0 genauso in s3 über wie bei einer 1. Drei weitere Symbole verstreichen, doch das Ergebnis stand für sie alle schon vorher fest. Ein Fangzustand ist die Methode eines DFA, sich vor dem Ende der Eingabe auf ein Ja festzulegen, ohne sich dabei den genauen Zeitpunkt zu merken.
kein 101 ✗ - Abgelehnt in s2, den die Legende als „10 gelesen, noch ein Symbol fehlt“ bezeichnet. Eine weitere 1 am Ende hätte das Muster vervollständigt und die Maschine für immer in s3 gesperrt. Der erreichte Zustand verrät dir, wie nah du dran warst. Das reine Akzeptieren oder Ablehnen allein kann das niemals.