Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · Abitur NRW Informatik LK · Nachtermin 2021

Ermitteln Sie die Ableitung von rrbrr und entscheiden Sie, ob das Wort zur Sprache gehört:

Lösung: Ableitung von $rrbrr$: $S \rightarrow rrA$ $\rightarrow rrbD$ $\rightarrow rrbrr$ Das Wort gehört zur Sprache der Grammatik $G$.

Ermitteln Sie den Ableitungsversuch von rrggr und entscheiden Sie, ob das Wort zur Sprache gehört:

Lösung: Ableitungsversuch von $rrggr$: $S \rightarrow rrA$ $\rightarrow rrgC$ $\rightarrow rrggD$ $\rightarrow$ ? Vom Nichtterminal $D$ lässt sich kein einzelnes $r$ ableiten. Eine andere Möglichkeit der Ableitung gibt es nicht. Daher gehört das Wort nicht zur Sprache der Grammatik $G$.

Ermitteln Sie die Ableitung von rrggrrbrr und entscheiden Sie, ob das Wort zur Sprache gehört:

Lösung: Ableitung von $rrggrrbrr$: $S \rightarrow rrA$ $\rightarrow rrgC$ $\rightarrow rrggD$ $\rightarrow rrgg \, rrA$ $\rightarrow rrgg \, rrbD$ $\rightarrow rrggrrbrr$ Das Wort gehört zur Sprache der Grammatik $G$.

Erläutern Sie, welchen allgemeinen Regeln die Zeilen der Mosaike folgen, deren darstellende Wörter aus der Grammatik G erzeugt werden können:

Lösung: Die Zeilen der Mosaike zur Grammatik $G$ beginnen und enden mit zwei roten Steinen, da die erste Produktion $S \rightarrow rrA$ zweimal das Zeichen $r$ produziert und die letzte Produktion $D \rightarrow rr$ ebenfalls zweimal das Zeichen $r$ produziert. Nach den ersten beiden Zeichen kann man bei den Produktionen von $A$ entscheiden, ob man mit $A \rightarrow bB$ oder $A \rightarrow bD$ ein oder mehrere $b$ oder mit $A \rightarrow gC$ oder $A \rightarrow gD$ ein oder mehrere $g$ produzieren möchte, bevor man zum Nichtterminal $D$ gelangt. Von $D$ aus kann man mit $rr$ enden oder mit $D \rightarrow rrA$ die Trennkennung $rr$ erzeugen und anschließend erneut die Entscheidung treffen, die man zu Anfang treffen konnte. Die produzierten Wörter beginnen also mit $rr$, dann folgt mindestens einmal, aber beliebig oft die folgende Kombination: eine beliebige Anzahl desselben Zeichens $b$ oder $g$ (mindestens aber eins) mit anschließendem $rr$.

d) Begründen Sie, weshalb sich kein endlicher Automat konstruieren lässt, der feststellen kann, ob ein Wort eine Zeile des Werks „MORGEN“ beschreibt:

Lösung: Es ist nicht möglich, einen endlichen Automaten zu konstruieren, der entscheiden kann, ob ein Wort eine regelkonforme Zeile des Werks „MORGEN“ darstellt, da der Automat hierfür die roten und gelben Steine zählen müsste und die Länge der Zeile nicht begrenzt ist. Endliche Automaten können nicht beliebig weit zählen, weil man je Zählwert einen eigenen Zustand benötigen würde, der diesen repräsentiert, endliche Automaten aber nur endlich viele Zustände haben.

d) Entwerfen Sie einen nichtdeterministischen Kellerautomaten, der genau diejenigen Wörter akzeptiert, die eine Steinzeile des Werks „MORGEN“ darstellen.

Lösung: Der folgende Kellerautomat $(Z, A, K, d, S, \#, E)$ erfüllt die Anforderungen: - Zustandsmenge: $Z = \{q_0, q_1, q_2, q_3, q_4\}$ - Eingabealphabet: $A = \{r, g, b\}$ - Kelleralphabet: $K = \{\#, R\}$ - Startzustand: $S = q_0$ - Kellerstartsymbol: $\#$ - Menge der Endzustände: $E = \{q_4\}$ Übergangsdiagramm: