Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik LK · Nachtermin 2021

Aufgabenstellung

Die Künstlerin Mosa Iks strebt mit ihren Werken nach Ruhm. Diese setzen sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b genauso aufeinanderfolgen wie die zugehörigen Farbsteine in der Zeile des Kunstwerks. Bereits sehr erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

a)

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

Entscheiden Sie für die Wörter grg, gbggg und rrg jeweils, ob sie eine zulässige Zeile des Werkes „GESTERN“ darstellen.

Entwickeln Sie für einen deterministischen endlichen Automaten das Zustandsübergangsdiagramm, sodass er exakt diejenigen Wörter akzeptiert, die im Werk „GESTERN“ zulässige Zeilen aus Mosaiksteinen darstellen.

b)

Das Mosaik „HEUTE“, das Mosa gerade anfertigt, setzt sich aus Zeilen von Mosaiksteinen zusammen, deren Wortdarstellungen vom folgenden deterministischen endlichen Automaten A erkannt werden:

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

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

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