Deterministischer endlicher Automat: Unterschied zwischen den Versionen
| (20 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 2: | Zeile 2: | ||
==='''Definition'''=== | ==='''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. | + | 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]] | ||
| Zeile 19: | Zeile 21: | ||
Ein DEA überprüft, ob ein Wort Element der Sprache ist. | Ein DEA überprüft, ob ein Wort Element der Sprache ist. | ||
| + | ==='''Darstellung'''=== | ||
| − | + | [[Datei:Übergangsdiagramm.jpg|417px|thumb|left|Übergangsdiagramm]] | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | <br><br><br><br><br><br><br><br><br><br><br><br> | ||
| + | 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. | ||
| + | <br> | ||
| + | [[Datei:Übergangstabelle.jpg|417px|thumb|left|Übergangstabelle]] | ||
| + | <br><br><br><br><br><br> | ||
==='''Beispielaufgabe:'''=== | ==='''Beispielaufgabe:'''=== | ||
| Zeile 34: | Zeile 39: | ||
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. <br> | 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. <br> | ||
Aufgabe 3 Entwerfen Sie den Übergangsgraphen des Automaten, der ein SOS-Signal erkennt. Geben Sie außerdem die Übergangstabelle an.<br> | Aufgabe 3 Entwerfen Sie den Übergangsgraphen des Automaten, der ein SOS-Signal erkennt. Geben Sie außerdem die Übergangstabelle an.<br> | ||
| − | |||
| + | |||
| + | ==='''Literaturverzeichnis:'''=== | ||
| + | |||
| + | Automaten auf See, Arbeitsblatt, Oktober 2015 | ||
[[Bild:Zustandstabelle1|Zustandstabelle]] | [[Bild:Zustandstabelle1|Zustandstabelle]] | ||
Aktuelle Version vom 12. Februar 2016, 14:05 Uhr
Inhaltsverzeichnis
Definition[Bearbeiten]
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[Bearbeiten]
Ein DEA überprüft, ob ein Wort Element der Sprache ist.
Darstellung[Bearbeiten]
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:[Bearbeiten]
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:[Bearbeiten]
Automaten auf See, Arbeitsblatt, Oktober 2015
