faecher:informatik:oberstufe:automaten:lepro:akzeptanzverhalten:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

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] sbelfaecher: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) ===== 
- 
-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. 
  • faecher/informatik/oberstufe/automaten/lepro/akzeptanzverhalten/start.1600771460.txt.gz
  • Zuletzt geändert: 22.09.2020 12:44
  • von sbel