Simulic
Deutsch

Endliche Automaten – Ampel, DFA, NFA und reguläre Sprachen

InformatikAlgorithmen und ProblemlösenAlter 15–16

Wird geladen …

Mit meiner Klasse nutzen ✨ Mit KI anpassen Problem melden

Führen Sie vorgegebene Zustandsautomaten (Ampel, Getränkeautomat, Drehkreuz) Schritt für Schritt durch eine Folge von Ereignissen und beobachten Sie den aktuellen Zustand, die Ausgabe und eine Tracetabelle; fügen Sie Zustände hinzu, verschieben und verbinden Sie sie, um einen eigenen Automaten zu zeichnen. Der Modus Akzeptor prüft, welche Wörter ein DFA oder NFA akzeptiert (durch 3 teilbare Binärzahlen, auf ab endende Wörter), mit Übergangstabelle, äquivalentem regulärem Ausdruck, äquivalenter regulärer Grammatik und der Umwandlung von NFA in DFA. Eine Notiz vergleicht jedes Modell mit dem realen System, um über Abstraktion zu sprechen.

Lektion: Endliche Automaten: Zustände, Zustandsübergänge und Ausgaben; deterministische und nichtdeterministische endliche Automaten; reguläre Ausdrücke und reguläre Grammatiken

Was sie zeigt

Ein endlicher Automat hat eine endliche Menge von Zuständen, einen Startzustand, ein Eingabealphabet und Zustandsübergänge der Form Zustand + Symbol → Folgezustand. Er merkt sich nichts außer seinem aktuellen Zustand. Ein Mealy-Automat erzeugt Ausgaben an den Übergängen, ein Moore-Automat ordnet die Ausgaben den Zuständen zu, und ein Akzeptor antwortet mit Ja oder Nein: Gehört ein Wort zu einer Sprache? Die von endlichen Automaten akzeptierten Sprachen sind genau die regulären Sprachen, die auch reguläre Ausdrücke und reguläre Grammatiken beschreiben. Jeder NFA (NEA) lässt sich mit der Potenzmengenkonstruktion in einen äquivalenten DFA (DEA) umwandeln.

So funktioniert es

Wählen Sie im Modus Automat mit Ausgabe einen Eintrag unter Beispielautomat und klicken Sie auf Schritt oder Abspielen, um die Symbole auf dem Band einzeln einzugeben; die Symbol-Schaltflächen senden zusätzliche Ereignisse. Wählen Sie im Modus Akzeptor einen Eintrag unter Beispiel-Akzeptor, geben Sie unter Wort zum Lesen ein Wort ein und gehen Sie es schrittweise durch; nutzen Sie dann Testen oder Akzeptierte Wörter auflisten. Öffnen Sie Automat bearbeiten, um Zustände hinzuzufügen, zu verschieben und zu verbinden, oder klicken Sie auf NFA in DFA umwandeln.

Einstellbare Parameter

  • Modus Automat mit Ausgabe, Akzeptor
  • Beispielautomat (Modus Automat mit Ausgabe) Ampel, Getränkeautomat, Drehkreuz
  • Beispiel-Akzeptor (Modus Akzeptor) DFA: durch 3 teilbare Binärzahlen, NFA: Wörter, die auf ab enden, DFA: Wörter, die auf ab enden, DFA: gerade Anzahl Einsen (Paritätsbit)
  • Wort zum Lesen (leer = Beispielwort)
  • Ablaufgeschwindigkeit 0,5–4 Symbole/s
  • Bereich „Automat bearbeiten“ öffnen

Fragen zum Erkunden

  1. Welche Details einer echten Ampel lässt das Modell weg, und warum ist das vertretbar?
  2. Akzeptiert der Automat für die Teilbarkeit durch 3 das Wort 110, wenn Sie es Zustand für Zustand verfolgen?
  3. Warum braucht der NFA für Wörter, die auf ab enden, weniger Übergänge als der äquivalente DFA?

Ähnliche Simulationen