Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik GK · Haupttermin · Weiterbildungskolleg 2023

Aufgabenstellung

Beim Snooker, einer Variante des Billards, liegen zu Beginn 15 rote Kugeln auf dem Tisch, die Rote (r) heißen, sowie 6 Kugeln in anderen Farben, die zusammen Farbige (f) genannt werden. Zusätzlich gibt es eine weiße Kugel, die Weiße (w), die ebenfalls auf dem Tisch liegt (vgl. Abbildung 1).

Ziel eines Spielzugs (auch „Stoß“ genannt) ist es, eine der anderen Kugeln durch Anstoßen der Weißen mit dem Billardstock so anzuspielen, dass diese Kugel nach der Kollision mit der Weißen eingelocht wird, d. h., diese Kugel fällt in eines der Löcher am Tischrand (die sogenannten „Taschen“).

Der Snookerschüler Jonte und sein Trainer Max spielen eine Trainingsform des Spiels, in der jede eingelochte Kugel unmittelbar wieder auf den Tisch gelegt wird.

Wer an der Reihe ist, muss beim ersten Stoß genau eine Rote einlochen. Gelingt dies, bleibt man am Spiel und man muss beim nächsten Stoß versuchen, genau eine Farbige einzulochen. Wenn auch dies gelingt, so darf man nun wie zuvor so lange abwechselnd Rote und Farbige einlochen, bis man einen Fehler macht.

Es gilt als Fehler, wenn die falsche Kugelsorte angespielt und eingelocht wird, wenn die weiße Kugel eingelocht wird oder wenn bei einem Stoß keine Kugel eingelocht wird. Auch fehlerhaft eingelochte Kugeln werden wieder auf die Anfangsposition auf den Tisch gelegt. Nach einem Fehler gibt es einen Spielerwechsel.

Vereinfachend gehen wir davon aus, dass nur folgende Ereignisse im Training eintreten:

Stoß (s) – Ein neuer Stoß beginnt durch das Anstoßen der Weißen mit dem Billardstock.

Nach dem Anstoßen der Weißen tritt genau eines der folgenden vier Ereignisse ein:

Eine rote Kugel wird angespielt und eingelocht (r).

Eine farbige Kugel wird angespielt und eingelocht (f).

Die weiße Kugel wird eingelocht (w).

Keine Kugel wird eingelocht (k).

Zusätzlich gehen wir davon aus, dass nie mehr als eine Kugel pro Stoß eingelocht wird.

In jedem Trainingsspiel hat Jonte den ersten Stoß. Die beiden spielen, bis sie aufhören möchten, wobei der letzte Stoß stets noch zum Spiel zählt.

Jonte und Max protokollieren ihre Spiele, um sie später für das weitere Training auszuwerten. Die Trainingsspiele werden protokolliert, indem die zu den Ereignissen gehörigen Buchstaben in der Reihenfolge ihres Auftretens notiert werden.

Beispiel für ein sehr kurzes Trainingsspiel: Jonte locht eine Rote und eine Farbige ein, beim dritten Stoß locht er keine Kugel ein. Max locht dann mit seinem ersten Stoß eine Rote ein. Das Protokoll dazu lautet: srsfsksr

Um eine Vielzahl von Protokollen auswerten zu können, wurde ein deterministischer endlicher Automat A dazu entworfen, um Spielprotokolle zu untersuchen. In Abbildung 2 ist sein Zustandsübergangsdiagramm dargestellt.

Anhang: Dokumentationen der verwendeten Klassen

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls (hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe a)

a.1)

Geben Sie für den Automaten $A$ die Zustandsmenge, die Menge der Endzustände sowie den Startzustand an.

a.2)

Ermitteln Sie ein vom Automaten $A$ akzeptiertes Wort, bei dessen Verarbeitung alle Zustände durchlaufen werden, und erläutern Sie, wie das Trainingsspiel verlief, das durch dieses Wort protokolliert wurde.

a.3)

Erläutern Sie im Sachzusammenhang, was die Zustände $q_0$, $q_2$ und $q_6$ bedeuten und wofür die von diesen drei Zuständen ausgehenden Übergänge stehen.

Teilaufgabe b)

Ein deterministischer endlicher Automat $B$ mit dem Eingabealphabet $\{f, k, r, s, w\}$ ist zu entwerfen. Als Eingabe erhält er garantiert nur gültige Spielprotokolle. Er soll genau diejenigen Eingaben akzeptieren, bei denen im zugehörigen Trainingsspiel sowohl Jonte als auch Max mindestens einmal gestoßen haben.

b.1)

Geben Sie das kürzestmögliche Wort eines Spielprotokolls an, in dem sowohl Jonte als auch Max mindestens einmal gestoßen haben.

b.2)

Geben Sie ein Wort der Länge 6 für ein Spielprotokoll an, in dem nur einer der beiden einen Stoß ausgeführt hat.

b.3)

Entwerfen Sie für den Automaten $B$ ein Zustandsübergangsdiagramm.