Deterministischer endlicher Automat: Unterschied zwischen den Versionen

Version vom 12. Februar 2016, 13:50 Uhr

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

d = Zustandsübergangsfunktion

q0 = Anfangszustand

E = Endzustände

L(M) = Sprache Deterministischer endlicher Automat

Funktion

Ein DEA überprüft, ob ein Wort Element der Sprache ist.

Darstellung

Übergangsdiagramm

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

Zustandstabelle