Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · Abitur NRW Informatik GK · Haupttermin · Weiterbildungskolleg 2021

Aufgabenstellung:

Leonard besucht einen Informatikkurs und plant, nach dem Abitur Informatik zu studieren. Beim Aufräumen des Dachbodens, wozu ihn seine Eltern auffordern, stößt er auf seine alte Modelleisenbahn, mit der er als Kind oft gespielt hat. Er weiß noch, dass er stets eine sinnvolle Schienenanlage bauen wollte, auf der die Bahn entweder im Kreis fährt oder an Prellböcken endet. Mit seinem Wissen aus der theoretischen Informatik will Leonard untersuchen, ob eine Schienenanlage sinnvoll aufgebaut ist. Um die Untersuchung überschaubar zu halten, nutzt er zunächst nur die folgenden Bauteile.

Ein endlicher Automat soll dazu dienen, zu überprüfen, ob eine Schienenanlage sinnvoll aufgebaut ist.

Hierfür reiht er die Bauteil-IDs zu Wörtern aneinander, die jeweils eine Schienenanlage repräsentieren. Eine Anlage aus zwei Prellböcken mit einer Brücke dazwischen wird zum Beispiel durch das Wort p1b2p beschrieben.

Zur Überprüfung von Schienenanlagen entwirft Leonard einen deterministischen endlichen Automaten A, dessen Zustandsübergangsdiagramm in Abbildung 2 zu sehen ist:

Anhang

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

Ab jetzt kommen keine Brücken und damit auch keine Auf- und Abfahrten mehr zum Einsatz; stattdessen stehen zusätzlich 90°-Kurvenelemente zur Verfügung:

c)

Die Sprache $L_G$ wird von der nachstehenden Grammatik $G$ erzeugt:

Startsymbol: $S$

Terminalsymbole: $\{g,\ r,\ l,\ p\}$

Nichtterminalsymbole: $\{S,\ G,\ K\}$

Produktionen:

$S \rightarrow pKp \mid pGp$,

$K \rightarrow rGl \mid lGr$,

$G \rightarrow gG \mid \varepsilon$

d)

Manche der kreisförmigen Schienenanlagen erinnern Leonard an „Ovale“. Ein „Oval“ entsteht folgendermaßen: Zuerst werden zwei Rechtskurven gebaut, danach eine bestimmte Anzahl $n$ gerader Gleisstücke, anschließend erneut zwei Rechtskurven und schließlich noch einmal $n$ gerade Gleisstücke.

Leonard möchte einen deterministischen endlichen Automaten erstellen, der feststellt, ob eine geplante Schienenanlage ein „Oval“ ist. Dabei stehen ihm beliebig viele Bauteile zur Verfügung.