Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · Abitur NRW Informatik GK · Haupttermin 2023

Aufgabenstellung:

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

Bei 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 sogenannten „Taschen“) fällt.

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

Der Spieler am Zug muss mit dem ersten Stoß genau eine Rote einlochen. Hat er damit Erfolg, bleibt er am Zug und muss mit dem nächsten Stoß genau eine Farbige einlochen. Gelingt auch das, setzt er das abwechselnde Einlochen von Roten und Farbigen fort, bis ihm ein Fehler unterläuft.

Ein Fehler liegt vor, wenn die falsche Kugelsorte angespielt und eingelocht wird, die Weiße eingelocht wird oder bei einem Stoß gar keine Kugel eingelocht wird. Auch bei einem Fehler werden eingelochte Kugeln auf ihre Anfangsposition zurückgelegt. Nach einem Fehler wechselt der Spieler.

Zur Vereinfachung nehmen wir an, dass im Training ausschließlich die folgenden Ereignisse auftreten:

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

Außerdem wird angenommen, dass pro Stoß höchstens eine Kugel eingelocht wird.

Jonte eröffnet jedes Trainingsspiel. Beide trainieren, bis sie aufhören möchten, wobei der letzte Stoß stets noch zum Spiel zählt.

Jonte und Max halten ihre Spiele in Protokollen fest, um sie später für das weitere Training auszuwerten. Dazu schreiben sie die Buchstaben der eingetretenen Ereignisse in zeitlicher Reihenfolge auf.

Beispiel für ein sehr kurzes Trainingsspiel: Jonte locht eine Rote und eine Farbige ein, bei seinem dritten Stoß fällt keine Kugel in eine Tasche. Anschließend locht Max mit seinem ersten Stoß eine Rote ein. Das zugehörige Protokoll lautet: srsfsksr

Zur Auswertung vieler Protokolle wurde ein deterministischer endlicher Automat A entworfen, der Spielprotokolle untersucht. Sein Zustandsübergangsdiagramm zeigt Abbildung 2.

c)

In manchen Trainingsspielen wird bei einem Stoß oft versehentlich die weiße Kugel versenkt. In anderen Spielen kommt dies höchstens ein einziges Mal im gesamten Spiel vor.

Entwerfen Sie eine reguläre Grammatik G, die genau diejenigen Wörter erzeugt, die Spielprotokolle darstellen, in denen die weiße Kugel höchstens einmal eingelocht wurde.

Entscheiden Sie, indem Sie in Ihrer entworfenen Grammatik G ableiten, ob die Zeichenketten srswsfsk und swsfsw zur Sprache von G gehören.

e)

Jonte und Max spielen nun eine Variante, in der die Reihenfolge der versenkten Kugelfarben keine Rolle spielt. Nur die versenkten roten Kugeln bleiben in den Taschen, versenkte farbige Kugeln kommen zurück auf das Spielfeld. Der Spieler wechselt, wenn bei einem Stoß keine Kugel oder die weiße Kugel eingelocht wird. Wer die letzte der 15 Roten einlocht, gewinnt.

Jonte behauptet, mit einem endlichen Automaten könne man ein korrekt geführtes Spielprotokoll daraufhin untersuchen, ob im zugehörigen Spiel alle 15 Roten eingelocht wurden.

Max hält das für unmöglich, da die Protokolle wegen der Spielerwechsel nach Fehlern beliebig lang werden können und endliche Automaten nicht unbegrenzt zählen können.

Beurteilen Sie, ob Jontes Behauptung zutrifft.