Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:start [22.09.2020 14:55] – [Erster Start] 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://www.jflap.org/|JFLAP]], das diese Untersuchung vereinfacht.((Auch im Moodle)).
-===== Teillernziele =====
-Nach der Bearbeitung dieses Kapitels kannst du ...
-  * die Begriffe „akzeptieren“ und „verwerfen“ verstehen und erläutern.
-  * untersuchen, ob ein Automat ein Wort akzeptiert oder verwirft.
-  * 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; sie wird genau dann von dem
-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**.
-</WRAP>
-Betrachte noch einmal den Automaten aus dem vorigen Abschnitt:
-{{ :faecher:informatik:oberstufe:automaten:lepro:darstellung:automat1.png?600 |}}
-Akzeptiert dieser Automat das Eingabewort ''bba''?
-  * 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 ''bba''.
-Akzeptiert der Automat auch das Wort ''bb''?
-Nach dem Lesen der Zeichenkette ''bb'' befindet sich der Automat im Zustand q3. Da q3 kein Endzustand
-ist, akzeptiert er das Wort ''bb'' nicht.
-===== Aufgabe(n) =====
-**(1)** Überprüfe, welche der folgenden Wörter der Automat aus dem obigen Beispiel
-akzeptiert!
-  * aaaaa
-  * b
-  * ca
-**(2)** Betrachte folgenden Automaten:
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:automat_a1.png |}}
-Überprüfe, welche der folgenden Wörter der Automat akzeptiert!
-  * ''aaaaaac''
-  * ''bccb''
-  * ''ba''
-====== 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, der über die Schüler mit Anfangsbuchstaben ''An'' Auskunft gibt.
-Das Eingabealphabet besteht aus allen Buchstaben des Alphabets: {a, A, b, B, ..., z, Z}. Dieser Automat
-akzeptiert das "Wort" ''Anna'' genau dann, wenn er nach Bearbeitung der Eingabe des Wortes in einem Endzustand
-landet. Verfolge die Reaktion des Automaten:
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:ausflug.png?600 |}}
-  * 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) =====
-**(1)** Welche Schüler, deren Namen mit An beginnt, dürfen auch noch mit auf den Schulausflug
-fahren? Nenne die Namen.
-**(2)** Anne und Anke wollen auch noch mit auf den Ausflug fahren. Sie melden sich deshalb an
-und bezahlen den Beitrag. Verifiziere, dass Anne und Anke nicht als Eingaben akzeptiert werden. Verändere den Automaten so, dass er auch die Eingaben Anne und Anke akzeptiert.
-====== Übungen mit JFLAP ======
-Nun wirst du dich mit der Simulation von Automaten beschäftigen. Das Programm [[http://www.jflap.org/|JFLAP]]
-ermöglicht dir, Automaten zu entwerfen und ihr Akzeptanzverhalten zu testen. Im folgenden Beispiel lernst du, JFLAP selber zu bedienen. Vollziehe die im Beispiel beschriebenen Schritte nach, um den Umgang mit dem Programm zu lernen.
-===== Erster Start =====
-JFLAP kommt als ''.jar''-Datei, diese kann man auf einer Konsole ausführen mit ''java -jar JFLAP7.1.jar''.
-Nach dem Start des Programms erscheint zunächst ein Fenster, in dem man die Art des
-Automaten auswählen kann. Da du dich erst einmal nur mit **endlichen Automaten** befasst, wählst du den Button **Finite Automaton**.
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:jflap1.png?300 |}}
-Es erscheint ein weiteres Fenster zur Erstellung des Automaten.
-Wie du einen Automaten erstellst, lernst du im nächsten Beispiel. Zunächst wirst du lernen, einen bereits erstellten Automaten zu testen.
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:jflap2.png |}}
-Gehe dazu im Menü auf ''File -> open'' und öffne die Datei ''Schulausflug.jff'', diese findest du in {{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:schulausflug.jff.zip |diesem ZIP-Archiv}}. Nun siehst du
-den Automaten aus dem Beispiel mit dem Schulausflug.
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:jflap_schulausflug_jff.png |}}
-Jetzt sollst du das Verhalten des Automaten testen. JFLAP bietet dafür zwei Möglichkeiten:
-**Möglichkeit 1:**
-Der Automat arbeitet das Wort schrittweise ab. Gehe dazu in der Menübar des bereits geöffneten Fensters auf ''Input->Step by State''. Es erscheint ein Eingabefenster. Gebe dort ''Anna'' ein.
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:anna1.png |}}
-Dann öffnet sich ein Fenster, in dem du das Verhalten des Automaten schrittweise nachvollziehen kannst, indem
-du auf den Button ''Step'' klickst. Um den Automaten erneut mit der gleichen Eingabe zu starten, musst du Reset drücken.
-{{ :faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:step.png |}}
-Starte nun auf gleiche Weise den Automaten einmal mit der Eingabe Anke und
-einmal mit der Eingabe Andreas. Dabei wirst du feststellen, dass der Automat
-sich bei der Eingabe Anke grün färbt; die Eingabe wird also akzeptiert. Die Eingabe Andreas kann der Automat dagegen nicht verarbeiten. Deshalb stoppt er bei ''q8'', egal wie oft der Step-Button jetzt noch gedrückt wird.