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

Aufgabenstellung:

Beim Snooker, einer Billard-Variante, liegen zu Beginn 15 rote Kugeln auf dem Tisch, Rote ($r$) genannt, und 6 Kugeln anderer Farben, die zusammenfassend als Farbige ($f$) bezeichnet werden. Darüber hinaus liegt noch eine weiße Kugel, genannt die Weiße ($w$), auf dem Tisch (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.

Jonte eröffnet jedes Trainingsspiel. Die beiden spielen, bis sie aufhören möchten, wobei der zuletzt ausgeführte Stoß stets noch zum Spiel zählt.

Jonte und Max halten ihre Spiele in Protokollen fest, damit sie diese später für ihr weiteres Training nutzen können. 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.

b)

In einigen Trainingsspielen wird bei einem Stoß immer wieder versehentlich die weiße Kugel versenkt. In anderen Spielen kommt dies höchstens einmal 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 aus Ihrer Grammatik $G$ ableiten, ob die Zeichenketten $srswsfsk$ und $swsfsw$ zur Sprache von $G$ gehören.

d)

Trainer Max ist ein routinierter Snookerspieler, dem Fehler wie das versehentliche Versenken der weißen Kugel kaum noch unterlaufen. Er verfolgt die Trainingsspiele aufmerksam und glaubt, dass Jonte die Weiße inzwischen seltener versehentlich einlocht.

Dies soll ein Kellerautomat anhand der Spielprotokolle überprüfen. Dazu schreibt er hinter ein aktuelles Spielprotokoll ein Trennzeichen $t$ und fügt anschließend ein älteres Spielprotokoll an.

Weil nur das Zeichen $w$ für ihn relevant ist, wird im gesamten Eingabewort jedes andere Zeichen als $w$ durch $z$ ersetzt.

Tritt $w$ im zweiten Protokoll (hinter dem Trennzeichen) öfter auf als im ersten (vor dem Trennzeichen), geht er von einer tatsächlichen Verbesserung Jontes aus.

Entwerfen Sie einen Kellerautomaten, der ein Eingabewort der beschriebenen Art verarbeitet und feststellt, ob sich Jonte beim direkten Vergleich der beiden betrachteten Trainingsspiele verbessert hat.

Laden Sie dazu ein Foto Ihres Zustandsübergangsdiagramms oder der formalen Definition Ihres Kellerautomaten hoch:

Stellen Sie dar, wie das Wort $zwtwww$ erkannt wird (z. B. als Tabelle der Konfigurationsschritte bzw. Kellerzustände).

e)

Jonte und Max spielen nun eine Variante, in der die Reihenfolge der versenkten Farben keine Rolle spielt. Nur versenkte rote Kugeln bleiben in den Taschen, versenkte farbige Kugeln kommen zurück aufs Spielfeld. Der Spieler wechselt, wenn bei einem Stoß keine Kugel oder die weiße Kugel eingelocht wird. Gewonnen hat, wer die letzte der 15 Roten versenkt.

Jonte behauptet, dass man ein korrekt protokolliertes Spielprotokoll mithilfe eines endlichen Automaten daraufhin untersuchen kann, ob bei dem dazugehö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 Jonte recht hat.