Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik LK · Haupttermin 2023

Aufgabenstellung:

Beim Snooker, einer Variante des Billards, liegen zu Beginn 15 rote Kugeln auf dem Tisch, Rote (r) genannt, sowie 6 Kugeln in anderen Farben, die gemeinsam als Farbige (f) bezeichnet werden. Zusätzlich befindet sich eine weiße Kugel, die Weiße (w) heißt, auf dem Tisch (vgl. Abbildung 1).

In einem Spielzug (auch „Stoß“ genannt) soll man mit dem Billardstock die Weiße so anstoßen, dass sie eine andere Kugel trifft und diese eingelocht wird, d. h. in eines der Löcher am Tischrand (die „Taschen“) fällt.

Snookerschüler Jonte und sein Trainer Max spielen eine Trainingsvariante des Spiels, bei der alle eingelochten Kugeln sofort wieder auf den Tisch zurückgelegt werden.

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.

Jonte beginnt alle Trainingsspiele. Er und sein Trainer trainieren so lange, bis sie keine Lust mehr haben. Dabei gehört das Ergebnis des letzten Stoßes immer zum Spiel dazu.

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.

a)

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

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 mit diesem Wort protokolliert wurde.

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

c)

Die Spielregeln werden erweitert. Unter bestimmten Bedingungen soll es zulässig sein, dass bei einem Stoß mehrere Kugeln in die Tasche fallen und es auf dem Spielfeld zu weiteren Kugelberührungen kommt:

Der Spieler am Zug muss nach dem ersten Stoß zunächst eine Rote einlochen; anschließend sind wie zuvor abwechselnd Farbige (zuerst) und Rote erlaubt.

Zudem muss mit jedem Stoß wenigstens eine Rote oder Farbige eingelocht werden.

Als Fehler gilt weiterhin, wenn die Weiße eingelocht wird oder wenn die Kugelsorten nicht abwechselnd oder in falscher Reihenfolge fallen (z. B. zuerst eine Farbige, obwohl eine Rote an der Reihe wäre).

Entworfen werden soll ein deterministischer endlicher Automat $B$ mit dem Eingabealphabet $\{f, k, r, s, w\}$, der genau dann ein Spielprotokoll akzeptiert, wenn im zugehörigen Trainingsspiel die erweiterten Regeln fehlerfrei eingehalten wurden.

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