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 JFLAP, das diese Untersuchung vereinfacht.1) 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.

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 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.