Deterministischer endlicher Automat: Unterschied zwischen den Versionen
(→Sprache Deterministischer endlicher Automat) |
|||
| Zeile 4: | Zeile 4: | ||
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. | 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 | + | A = [[Eingabealphabet]] |
| − | Z = Zustände | + | Z = [[Zustände]] |
| − | d = Zustandsübergangsfunktion | + | d = [[Zustandsübergangsfunktion]] |
| − | q0 = Anfangszustand | + | q0 = [[Anfangszustand]] |
| − | E = Endzustände | + | E = [[Endzustände]] |
L(M) = [[Sprache Deterministischer endlicher Automat]] | L(M) = [[Sprache Deterministischer endlicher Automat]] | ||
| + | |||
==='''Funktion'''=== | ==='''Funktion'''=== | ||
Version vom 3. Dezember 2015, 22:53 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
q0 = Anfangszustand
E = Endzustände
L(M) = Sprache Deterministischer endlicher Automat
Funktion
Ein DEA überprüft, ob ein Wort Element der Sprache ist.
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.
(Quelle:Automaten auf See, Arbeitsblatt, Oktober 2015)
