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

Aufgabenstellung

Die Künstlerin Mosa Iks strebt Ruhm mit Kunstwerken an, die sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammensetzen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b in der gleichen Abfolge stehen wie die zugehörigen Farbsteine in der Zeile. Bereits besonders erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

Anhang

Dokumentation ausgewählter Methoden der Klasse String

char charAt(int index) Die Anfrage gibt das Zeichen am angegebenen Index zurück. Der Index hat einen Wertebereich von 0 bis length() - 1. Das erste Zeichen dieser Zeichenkette ist an Index 0, das nächste an Index 1 und so weiter, wie bei Array-Indizes.

int compareTo(String anotherString) Die Methode vergleicht zwei Zeichenketten lexikografisch. Sie liefert einen Integerwert kleiner als 0, wenn der String lexikografisch vor der übergebenen Zeichenkette anotherString anzuordnen ist. Sie liefert einen Integerwert größer als 0, wenn der String lexikografisch nach der der übergebenen Zeichenkette anotherString anzuordnen ist. Sind beide Zeichenketten identisch, wird der Wert 0 zurückgegeben.

boolean equals(Object anObject) Die Methode liefert genau dann true, wenn das übergebene Objekt anObject nicht null ist und wenn es vom Typ String ist und die gleiche Zeichenkette repräsentiert.

int indexOf(String str) Die Methode liefert den Index des ersten Zeichens beim ersten Vorkommen der übergebenen Zeichenkette str. Kommt die übergebene Zeichenkette nicht vor, wird -1 zurückgegeben.

int length() Die Methode liefert die Länge der Zeichenkette.

boolean startsWith(String prefix) Die Methode liefert genau dann den Wert true, wenn die Zeichenkette mit dem angegebenen Präfix prefix beginnt. Andernfalls liefert sie den Wert false. Wird eine leere Zeichenkette oder die identische Zeichenkette übergeben, liefert die Methode ebenfalls den Wert true.

String substring(int beginIndex) Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Ende der Zeichenkette. Der Wert des Parameters beginIndex darf nicht größer als die Länge des Zeichenkette sein. Ist er gleich der Länge der Zeichenkette, so wird die leere Zeichenkette "" zurückgegeben.

String substring(int beginIndex, int endIndex) Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Zeichen an Position endIndex - 1. Der Wert des Parameters endIndex darf nicht größer als die Länge des Strings sein. Der Wert des Parameters beginIndex muss größer oder gleich 0 sein und darf nicht größer als der Wert von endIndex sein.

Die Künstlerin plant, Abwandlungen des Kunstwerks „HEUTE“ zu schaffen. Mit einer regulären Grammatik will sie dazu beliebige Wörter der Sprache generieren, die jeweils Zeilen des Kunstwerks „HEUTE“ darstellen. Der zugehörige deterministische endliche Automat $A$ ist in Abbildung 2 angegeben:

c)

Entwerfen Sie eine reguläre Grammatik, die genau die vom Automaten $A$ akzeptierten Wörter erzeugt.

Vor einiger Zeit hat die Künstlerin ein Mosaik gestaltet, dessen Zeilen aus genau 4 oder 5 Steinen bestehen. Deshalb nannte sie es „VIERFÜNF“.

Die Wörter, welche diese Zeilen darstellen, entsprechen genau den Wörtern, die die folgende Grammatik $G_{45}$ erzeugt:

Startsymbol: S

Nichtterminale: N = {S, A, B}

Terminale: T = {r, g, b}

Produktionen: P = {

S -> rAr | gAg | bAb,

A -> rBr | gBg | bBb,

B -> r | g | b | ε

}

d) 1.

Erläutern Sie, aus welchem Grund jedes Wort, das die Grammatik $G_{45}$ erzeugt, genau 4 oder 5 Zeichen lang ist.

d) 2.

Ermitteln Sie für die folgenden Wörter jeweils die Ableitung und entscheiden Sie anhand dieser, ob die Wörter von der Grammatik $G_{45}$ erzeugt werden können: ggggg, rrbb.

d) 3.

Erläutern Sie, nach welchen allgemeinen Regeln die Zeilen der Mosaike aufgebaut sind, deren Wörter sich mit der Grammatik $G_{45}$ erzeugen lassen.

d) 4.

Begründen Sie, aus welchem Grund die Grammatik $G_{45}$ keine reguläre Grammatik darstellt.

d) 5.

Beurteilen Sie, ob eine reguläre Grammatik existiert, die genau die Wörter erzeugt, welche auch die Grammatik $G_{45}$ erzeugt.