Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:start [22.09.2020 12:44] – [Der Schulausflug] sbel | faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Akzeptanzverhalten von Automaten ====== | ||
- | ===== Übersicht ===== | ||
- | |||
- | Ein Automat soll Eingaben bezüglich bestimmter Eigenschaften unterscheiden. Dies | ||
- | wird realisiert durch das **Akzeptanzverhalten** des Automaten, das in diesem Kapitel genauer unter die Lupe genommen wird. Demonstriert wird dies mit Hilfe des Programms [[http:// | ||
- | |||
- | ===== Teillernziele ===== | ||
- | |||
- | Nach der Bearbeitung dieses Kapitels kannst du ... | ||
- | |||
- | * die Begriffe „akzeptieren“ und „verwerfen“ verstehen und erläutern. | ||
- | * untersuchen, | ||
- | * Automatenmodelle in JFLAP überführen und testen. | ||
- | |||
- | ====== Akzeptanzverhalten ====== | ||
- | |||
- | Die Aufgabe eines Automaten besteht oft darin, eine Eingabe auf Korrektheit zu überprüfen. Eine Eingabe besteht aus einer Folge von Zeichen aus dem Eingabealphabet; | ||
- | Automaten akzeptiert, wenn der Automat einen Endzustand erreicht. | ||
- | <WRAP center round important 80%> | ||
- | |||
- | **Definition** | ||
- | |||
- | Der Automat **akzeptiert** das Eingabewort genau dann, wenn er sich nach dem Einlesen | ||
- | des ganzen Wortes in einem **Endzustand** befindet. Ansonsten akzeptiert er das Wort | ||
- | nicht. Man sagt deshalb auch, dass der Automat in diesem Fall das Eingabewort **verwirft**. | ||
- | </ | ||
- | |||
- | Betrachte noch einmal den Automaten aus dem vorigen Abschnitt: | ||
- | |||
- | {{ : | ||
- | |||
- | Akzeptiert dieser Automat das Eingabewort '' | ||
- | |||
- | * Start bei q1. | ||
- | * b wird gelesen -> Wechsel zu q2 | ||
- | * zweites b wird gelesen -> Wechsel in q3 | ||
- | * a wird gelesen -> Wechsel zu q4 | ||
- | * | ||
- | Nach dem Einlesen der Zeichenfolge befindet sich der Automat im Endzustand q4. Also akzeptiert er | ||
- | das Word '' | ||
- | |||
- | Akzeptiert der Automat auch das Wort '' | ||
- | |||
- | Nach dem Lesen der Zeichenkette '' | ||
- | ist, akzeptiert er das Wort '' | ||
- | |||
- | ===== Aufgabe(n) ===== | ||
- | |||
- | |||
- | **(1)** Überprüfe, | ||
- | akzeptiert! | ||
- | |||
- | * aaaaa | ||
- | * b | ||
- | * ca | ||
- | |||
- | **(2)** Betrachte folgenden Automaten: | ||
- | |||
- | {{ : | ||
- | |||
- | Überprüfe, | ||
- | |||
- | * '' | ||
- | * '' | ||
- | * '' | ||
- | |||
- | ====== Der Schulausflug ====== | ||
- | |||
- | Alle Oberstufenschülerinnen und -schüler des Gymnasiums in Poppelsdorf machen einen Schulausflug. Die Schüler, die sich angemeldet und den Beitrag bezahlt haben, stehen auf einer Liste. | ||
- | |||
- | Der Schulcomputer verfügt über ein Programm, das nach der Eingabe eines Namens anzeigt, ob der | ||
- | Schüler bzw. die Schülerin mit auf den Ausflug kommen kann oder nicht. Das Programm simuliert also | ||
- | einen Automaten. | ||
- | |||
- | Anna ist sich nicht mehr sicher, ob sie wirklich das Geld für den Ausflug bezahlt hat. | ||
- | |||
- | Deswegen tippt sie ihren Namen in den Computer ein. | ||
- | |||
- | Du wirst dich nun mit dem Teil des Automaten beschäftigen, | ||
- | |||
- | Das Eingabealphabet besteht aus allen Buchstaben des Alphabets: {a, A, b, B, ..., z, Z}. Dieser Automat | ||
- | akzeptiert das " | ||
- | landet. Verfolge die Reaktion des Automaten: | ||
- | |||
- | {{ : | ||
- | |||
- | * Start in q0 | ||
- | * A wird gelesen -> Wechsel zu q1 | ||
- | * n wird gelesen -> Wechsel zu q2 | ||
- | * n wird gelesen -> Wechsel zu q3 | ||
- | * a wird gelesen -> Wechsel zu q9 | ||
- | |||
- | Da q9 ein Endzustand ist, akzeptiert der Automat die Eingabe Anna. Anna darf also mitfahren. | ||
- | |||
- | ===== Aufgabe(n) ===== | ||
- | |||
- | Welche Schüler, deren Namen mit An beginnt, dürfen auch noch mit auf den Schulausflug | ||
- | fahren? Nenne die Namen. | ||
- | Aufgabe 3.4 | ||
- | Anne und Anke wollen auch noch mit auf den Ausflug fahren. Sie melden sich deshalb an | ||
- | und bezahlen den Beitrag. Verändere den Automaten so, dass er auch die Eingaben Anne | ||
- | und Anke akzeptiert. |