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

c.1) Zeigen Sie, dass $rrggrrgg$ ein Wort ist, das sich mit der Grammatik $G$ ableiten lässt, während dies für das Wort $rrrr$ nicht gelingt.

Lösung: Ableitung des Wortes $rrggrrgg$: $$S \rightarrow rrA \rightarrow rrgBg \rightarrow rrggBgg \rightarrow rrggrrgg$$ Versuchte Ableitung des Wortes $rrrr$: $$S \rightarrow rrA$$ Aus dem Nichtterminal $A$ lässt sich nur eine Zeichenfolge ableiten, die das Terminal $g$ enthält ($A \rightarrow gBg$). Da $g$ im Wort $rrrr$ nicht vorkommt, lässt sich das Wort $rrrr$ nicht ableiten.

c.2) Erläutern Sie im Sachzusammenhang, für welche Schienenanlagen die Sprache $L_G$ steht.

Lösung: Durch die Grammatik können Wörter erzeugt werden, die Schienenanlagen darstellen, die mit einem Halbkreis aus zwei Rechtskurven beginnen, dann eine Anzahl $n > 0$ gerader Gleisstücke haben, anschließend wieder einen Halbkreis aus zwei Rechtskurven, zum Schluss dann wieder dieselbe Anzahl $n$ gerader Gleisstücke. Insgesamt haben die Schienenanlagen die Form eines Ovals, ähnlich einer Laufbahn im Stadion.

c.3) Begründen Sie, weshalb $G$ keine reguläre Grammatik ist.

Lösung: Die Grammatik $G$ ist nicht regulär, weil z. B. auf der rechten Seite der Produktion $A \rightarrow gBg$ rechts und links vom Nichtterminal jeweils ein Terminal steht. Das widerspricht den Regeln für Produktionen rechts- oder linksregulärer Grammatiken.

c.4) Entwickeln Sie einen Kellerautomaten, der die Sprache $L_G$ erkennt.

Lösung: Zustandsübergangsdiagramm des Kellerautomaten $M$ für die Sprache $L_G$: - Zustandsmenge: $\{q_0, q_1, q_2, q_3, q_4, q_5, q_6\}$ - Eingabealphabet: $\{r, g\}$ - Kelleralphabet: $\{G, \#\}$ - Anfangszustand: $q_0$ - Kellerstartsymbol: $\#$ - Menge der Endzustände: $\{q_6\}$ - Übergänge: * $(q_0, r, \#) \rightarrow (q_1, \#)$ * $(q_1, r, \#) \rightarrow (q_2, \#)$ * $(q_2, g, \#) \rightarrow (q_3, G\#)$ * $(q_3, g, G) \rightarrow (q_3, GG)$ * $(q_3, r, G) \rightarrow (q_4, G)$ * $(q_4, r, G) \rightarrow (q_5, G)$ * $(q_5, g, G) \rightarrow (q_5, \epsilon)$ * $(q_5, \epsilon, \#) \rightarrow (q_6, \#)$

e) Beurteilen Sie, ob ein endlicher Automat entscheiden kann, ob ein Wort eine Schienenanlage in Form eines „Quadrats“ beschreibt.

Lösung: Will man einen endlichen Automaten für diese Aufgabe konstruieren, so muss dieser in den Zuständen die Anzahl der geraden Gleisstücke für die erste Seite des Quadrats speichern, damit der Automat für die zweite Seite des Quadrats nach derselben Anzahl gerader Gleisstücke die nächste Kurve erwarten kann. Da Leonard beliebig große „Quadrate“ zulassen möchte, ist die Anzahl gerader Gleisstücke, und damit die Anzahl der Zustände nach oben unbegrenzt. Endliche Automaten dürfen aber nur eine endliche Anzahl Zustände besitzen. Daher kann es keinen solchen endlichen Automaten geben.