Deterministischer endlicher Automat: Unterschied zwischen den Versionen
| Zeile 1: | Zeile 1: | ||
| − | '''Definition''' | + | ==='''Definition'''=== |
| − | Ein deterministischer endlicher Automat 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 | ||
| Zeile 10: | Zeile 10: | ||
E = Endzustände | E = Endzustände | ||
| − | '''Funktion''' | + | ==='''Funktion'''=== |
| + | |||
Ein DEA überprüft, ob ein Wort Element der Sprache ist. | Ein DEA überprüft, ob ein Wort Element der Sprache ist. | ||
| + | ==='''Sprache Deterministischer endlicher Automat'''=== | ||
| − | '''Beispielaufgabe:''' | + | Alle Wörter, die von dem deterministischen endlichen Automaten akzeptiert werden, sind Teil seiner Sprache [L(M)]. |
| + | Ein Wort ist Teil der Sprache, wenn der deterministische endliche Automat durch eine Eingabefolge in seinen Endzustand gelangt. | ||
| + | |||
| + | |||
| + | ==='''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. | 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. | ||
| Zeile 23: | Zeile 29: | ||
(Quelle:Automaten auf See, Arbeitsblatt, Oktober 2015) | (Quelle:Automaten auf See, Arbeitsblatt, Oktober 2015) | ||
| − | |||
| − | |||
| − | |||
[[Bild:Zustandstabelle1|Zustandstabelle]] | [[Bild:Zustandstabelle1|Zustandstabelle]] | ||
Version vom 3. Dezember 2015, 22:34 Uhr
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 d = Zustandsübergangsfunktion q0 = Anfangszustand E = Endzustände
Funktion
Ein DEA überprüft, ob ein Wort Element der Sprache ist.
Sprache Deterministischer endlicher Automat
Alle Wörter, die von dem deterministischen endlichen Automaten akzeptiert werden, sind Teil seiner Sprache [L(M)]. Ein Wort ist Teil der Sprache, wenn der deterministische endliche Automat durch eine Eingabefolge in seinen Endzustand gelangt.
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)
