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:39] – [Akzeptanzverhalten] 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 ===== | ||
- | |||
- | |||
- | **(1)** Überprüfe, | ||
- | akzeptiert! | ||
- | |||
- | * aaaaa | ||
- | * b | ||
- | * ca | ||
- | |||
- | **(2)** Betrachte folgenden Automaten: | ||
- | |||
- | {{ : | ||
- | |||
- | Überprüfe, | ||
- | |||
- | * '' | ||
- | * '' | ||
- | * '' |