Determinierter endlicher Automat (DEA)
Ein determinierter endlicher Automat (DEA) ist ein 5-Tupel A = (Q, S, δ, q0, F) mit
- Q = endliche Menge von Zuständen
- S = Eingabealphabet
- δ = Übergangsfunktion
- q0 = Startzustand
- F = endliche Menge von Endzuständen.
Das ist die allgemein gültige Definition eines determinierten endlichen Automaten.
Eine ausführlichere Beschreibung finden Sie unter "Weiterführende Links" am Ende dieser Seite.
Abituraufgaben
DEAs sind bisher in fast jedem Abiturjahrgang in einer Aufgabe vorgekommen. Wenn Sie vorhaben, Informatik als mündliches oder schriftliches Abiturfach zu wählen, sollten sie in der Lage sein, vorgegebene DEAs zu beschreiben und zu analysieren, zum Beispiel was macht der Automat überhaupt, welche Sprache hat er und so weiter. Außerdem sollten Sie in der Lage sein, den vorgegebenen DEA zu erweitern, so dass er zusätzliche Aufgaben erfüllen kann. Das Umwandeln einer graphischen Darstellung des DEA in eine tabellarische Übersicht sollte Ihnen ebenfalls geläufig sein. Und in letzter Zeit wird in den schriftlichen Abituraufgaben immer wieder verlangt, dass man einen DEA in eine reguläre Grammatik umwandelt oder umgekehrt. Mit dem Konzept des nicht-determinierten endlichen Automaten (NEA oder NDEA) sollten Sie ebenfalls vertraut sein.
Determinierte endliche Automaten (DEAs) spielen in folgenden Abituraufgaben des Landes NRW eine wichtige Rolle:
2021 HT 4 - Modelleisenbahn. Gültige Gleisanlagen sollen mit Hilfe eines DEAs analysiert / konstruiert werden.
Weiterführende Links
"Determinierte endliche Automaten", eine sehr ausführliche und schülergerechte Darstellung auf u-helmich.de
"Endliche Automaten", eine sehr übersichtliche Darstellung auf der Seite des Hasso-Plattner-Instituts
"Endliche Automaten", eine recht anspruchsvolle Abhandlung auf der Seite der Uni Hamburg
"Endliche Automaten" auf StudyFlix.de, eine sehr übersichtliche Darstellung mit einem Videofilm
"Endliche Automaten" auf YouTube.com, eine ganze Liste von guten (und schlechten) Videos über endliche Automaten.