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

Thema: Grammatiken, Kellerautomaten und Grenzen endlicher Automaten · Aus der Prüfung LK · Haupttermin (2023)

Aufgabenstellung

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.

In einigen Trainingsspielen wird bei einem Stoß recht oft versehentlich die weiße Kugel versenkt. In anderen Spielen kommt dies höchstens ein einziges Mal pro Trainingsspiel 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 durch Ableiten in Ihrer Grammatik $G$ , ob die Zeichenketten srswsfsk und swsfsw in der Sprache von $G$ enthalten sind.

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

Dies will er mit einem Kellerautomaten überprüfen lassen. Hierzu schreibt er hinter ein aktuelles Spielprotokoll das Trennzeichen t und anschließend ein älteres Spielprotokoll.

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 Protokoll (vor dem Trennzeichen), geht er von einer tatsächlichen Verbesserung Jontes aus.

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

Stellen Sie dar, wie das Wort zwtwww erkannt wird.

Nun spielen Jonte und Max eine Variante, in der die Reihenfolge der eingelochten Farben keine Rolle spielt. Nur eingelochte rote Kugeln bleiben in den Taschen, eingelochte farbige Kugeln kommen zurück aufs Spielfeld. Der Spieler wechselt, wenn ein Stoß keine Kugel oder die weiße Kugel versenkt. Wer die letzte der 15 Roten einlocht, gewinnt.

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 Jontes Behauptung zutrifft.

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

Lösung

Nach den offiziellen Korrekturhinweisen

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

Lösung: Startsymbol: $S_G$ Nichtterminale: $N = \{S_G, A, B, C\}$ Terminale: $T = \{f, k, r, s, w\}$ Produktionen: $\begin{aligned} P = \{ & S_G \to sA, \\ & A \to fS_G \mid kS_G \mid rS_G \mid wB \mid f \mid k \mid r \mid w, \\ & B \to sC, \\ & C \to fB \mid kB \mid rB \mid f \mid k \mid r \} \end{aligned}$

b) Entscheiden Sie durch Ableiten in Ihrer Grammatik G, ob die Zeichenketten srswsfsk und swsfsw in der Sprache von G enthalten sind.

Lösung: Ableitung des Wortes srswsfsk: $S \to sA \to srS_G \to srsA \to srswB \to srswsC \to srswsfB \to srswsfsC \to srswsfsk$ Das Wort gehört zur Sprache der Grammatik. Versuchte Ableitung des Wortes swsfsw: $S \to sA \to swB \to swsC \to swsfB \to swsfsC \to ?$ Es gibt keine Produktion mit dem Nichtterminal $C$ auf der linken Seite, dessen rechte Seite mit dem Terminal $w$ beginnt. Das Wort gehört nicht zur Sprache der Grammatik.

d) Entwerfen Sie einen Kellerautomaten, der ein Eingabewort der beschriebenen Form verarbeitet und entscheidet, ob sich Jonte beim direkten Vergleich der beiden betrachteten Trainingsspiele verbessert hat.

Lösung: Zustandsmenge: $\{q_0, q_1, q_2\}$ Eingabealphabet: $\{z, w, t\}$ Kelleralphabet: $\{\#, W\}$ Anfangszustand: $q_0$ Kellerstartsymbol: $\#$ Menge der Endzustände: $\{q_2\}$

d) Formale Definition des Kellerautomaten (Zustandsmenge, Eingabealphabet, Kelleralphabet, Anfangszustand, Kellerstartsymbol, Endzustände, Übergangsfunktion)

Lösung: Zustandsmenge: $\{q_0, q_1, q_2\}$ Eingabealphabet: $\{z, w, t\}$ Kelleralphabet: $\{\#, W\}$ Anfangszustand: $q_0$ Kellerstartsymbol: $\#$ Menge der Endzustände: $\{q_2\}$ Übergangsfunktion $\delta$ : - Im Zustand $q_0$ : - $(\#, w) : W\#$ - $(W, w) : WW$ - $(\#, z) : \#$ - $(W, z) : W$ - $(\#, t) : \# \to q_1$ - $(W, t) : W \to q_1$ - Im Zustand $q_1$ : - $(W, w) : \varepsilon$ - $(\#, z) : \#$ - $(W, z) : W$ - $(\#, w) : \# \to q_2$ - Im Zustand $q_2$ : - $(\#, w) : \#$ - $(\#, z) : \#$

d) Stellen Sie dar, wie das Wort zwtwww erkannt wird.

Lösung: | Zustand | Gelesenes Eingabesymbol | Kellerinhalt / oberstes Symbol | Neuer Kellerinhalt / oberstes Symbol | Neuer Zustand | | :---: | :---: | :---: | :---: | :---: | | $q_0$ | $z$ | $\#$ | $\#$ | $q_0$ | | $q_0$ | $w$ | $\#$ | $W$ | $q_0$ | | $q_0$ | $t$ | $W$ | $W$ | $q_1$ | | $q_1$ | $w$ | $W$ | $\#$ | $q_1$ | | $q_1$ | $w$ | $\#$ | $\#$ | $q_2$ | | $q_2$ | $w$ | $\#$ | $\#$ | $q_2$ |

e) Beurteilen Sie, ob Jontes Behauptung zutrifft.

Lösung: Jonte ist im Recht. Solch einen Automaten kann man entwickeln. Der Automat könnte dabei diese Strategie verfolgen: - Der Automat verbleibt im Startzustand $q_0$ , solange er eines der Zeichen $k$ , $w$ , $f$ oder $s$ liest, und er wechselt in den Zustand $q_1$ , wenn er das Zeichen $r$ liest. - Analog verhält er sich im Zustand $q_1$ als neuem „Startzustand“ und allen folgenden Zuständen. - So geht es weiter bis zur 15. Roten. Ist also der Zustand $q_{15}$ erreicht, so akzeptiert der Automat das gelesene Wort. Der so beschriebene Automat hat endlich viele Zustände (nämlich 16 Zustände $q_0$ bis $q_{15}$ ) und akzeptiert, wenn 15 Mal das Zeichen $r$ gelesen wurde.

Die ausführliche Erklärung Schritt für Schritt (mit KI) gibt es mit Premium. Premium

Löse sie direkt hier: automatische Korrektur, Hinweise und Lösung Schritt für Schritt.

‹ Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · GK · Nachtermin 2023 · Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · LK · Haupttermin · Weiterbildungskolleg 2023 ›

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

Aufgabenstellung

Lösung

Mehr Aufgaben zu Grammatiken, Kellerautomaten und Grenzen endlicher Automaten