Dies ist eine alte Version des Dokuments!
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).
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.
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:
Überprüfe, welche der folgenden Wörter der Automat akzeptiert!
aaaaaacbccbba