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.

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.

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.

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.

Überprüfe, welche der folgenden Wörter der Automat aus dem obigen Beispiel akzeptiert!

• aaaaa
• b
• ca

Überprüfe, welche der folgenden Wörter der Automat akzeptiert!

• aaaaaac
• bccb
• ba

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:

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

Welche Schüler, deren Namen mit An beginnt, dürfen auch noch mit auf den Schulausflug fahren? Nenne die Namen.

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.