Aufgabe 4 - Endliche Automaten · 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.

a)

Kennzeichnend für das Werk „GESTERN“ ist, dass in jeder Zeile eines Mosaiks ausschließlich rote und gelbe Steine liegen, blaue dagegen nicht. Jede Zeile umfasst mindestens zwei Steine; dabei hat der letzte Stein (der ganz rechts liegende) eine Farbe, die weiter links in derselben Zeile schon mindestens einmal vorkommt. Im Folgenden wird jede Zeile für sich betrachtet.

Entscheiden Sie, ob es sich bei den Wörtern grg, gbggg und rrg um Wörter handelt, die zulässige Zeilen des Werkes „GESTERN“ darstellen.

Entwickeln Sie das Zustandsübergangsdiagramm eines deterministischen endlichen Automaten, der genau diejenigen Wörter akzeptiert, die zulässige Mosaiksteinzeilen im Werk „GESTERN“ darstellen.

[9 Punkte]

b)

Mosa arbeitet gerade am Mosaik „HEUTE“. Die Wortdarstellungen der Steinzeilen dieses Mosaiks erkennt der folgende deterministische endliche Automat A:

Geben Sie für den Automaten A die Zustandsmenge, die Menge der Endzustände sowie den Startzustand an.

Ermitteln Sie zum Zustandsübergangsdiagramm aus Abbildung 2 ein Wort der Länge 8, das der Automat A akzeptiert, und ein Wort der Länge 8, das der Automat A nicht akzeptiert.

Erläutern Sie, was der Zustand $q_3$ im Sachzusammenhang bedeutet.

[8 Punkte]