Deterministischer endlicher Automat
Inhaltsverzeichnis
Definition
Ein deterministischer endlicher Automat (DEA) ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabets ( den mögl. Eingaben ) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt.
A = Eingabealphabet
Z = Zustände
q0 = Anfangszustand
E = Endzustände
L(M) = Sprache Deterministischer endlicher Automat
Funktion
Ein DEA überprüft, ob ein Wort Element der Sprache ist.
Darstellung
Eine andere Form der Darstellung ist die Übergangstabelle.
Sie ist die tabellarische Darstellung der Übergangsfunktion. Der Startzustand wird durch ein Pfeil markiert, während der Endzustand durch einen Stern markiert wird.
Beispielaufgabe:
Automaten auf See Ein SOS-Erkennungs-Automat Schiffe in Seenot senden die Notruffolge „SOS“ aus. Damit ein Schiffskoch, der bei seiner Reederei Currysosse bestellt nicht versehentlich Alarm auslöst, sollen SOS-Rufe von Leerzeichen eingerahmt werden. Ein Automat in der Zentrale soll alle Nachrichten überprüfen und bei einem erkannten SOSSignal die Rettungswache alarmieren.
Aufgabe 1 Ordnen Sie dem gegebenen Problem einen Automatentypen zu. Begründen Sie Ihre Wahl.
Aufgabe 2 Geben Sie die Automatendefinition an. Ermitteln Sie dazu alle Elemente und Mengen des Automaten-Tupels. Ignorieren Sie alle Zeichen, die nicht zur Zeichenfolge gehören.
Aufgabe 3 Entwerfen Sie den Übergangsgraphen des Automaten, der ein SOS-Signal erkennt. Geben Sie außerdem die Übergangstabelle an.
Literaturverzeichnis:
Automaten auf See, Arbeitsblatt, Oktober 2015
