Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik GK · Haupttermin 2021

Aufgabenstellung: Analyse von Schienenanlagen einer Modelleisenbahn

Leonard besucht einen Informatikkurs und plant, nach dem Abitur Informatik zu studieren. Beim Aufräumen des Dachbodens, worum ihn seine Eltern gebeten haben, entdeckt er seine alte Eisenbahn, mit der er in der Kindheit oft gespielt hat. Ihm fällt ein, dass er stets eine sinnvolle Schienenanlage bauen wollte, auf der die Eisenbahn entweder im Kreis fährt oder die an beiden Enden durch Prellböcke abgeschlossen ist. Mit seinem Wissen aus der theoretischen Informatik will Leonard untersuchen, ob eine Schienenanlage sinnvoll aufgebaut ist. Um die Analyse überschaubar zu halten, nutzt er zunächst nur die folgenden Bauteile.

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

Hierfür fügt er die Bauteil-IDs zu Wörtern zusammen, die jeweils eine Schienenanlage repräsentieren. So wird beispielsweise eine Schienenanlage, die aus zwei Prellböcken und einer dazwischenliegenden Brücke besteht, durch das Wort p1b2p dargestellt.

Leonard entwickelt das in Abbildung 2 dargestellte Zustandsübergangsdiagramm eines deterministischen endlichen Automaten A zum Überprüfen von Schienenanlagen:

Im weiteren Verlauf kommen keine Brücken und damit auch keine Auf- und Abfahrten mehr vor, stattdessen werden zusätzlich 90°-Kurvenelemente verwendet:

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 gibt ( 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.

Teilaufgabe a)

Erläutern Sie, über welche Eigenschaften diejenigen Schienenanlagen verfügen, die den vom Automaten A akzeptierten Wörtern entsprechen.

Ermitteln Sie sämtliche Wörter minimaler Länge, die vom Automaten A akzeptiert werden und in denen jede Bauteil-ID mindestens einmal vorkommt.

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

Teilaufgabe b)

Das Wort pp gehört zur Sprache $L_A$ des Automaten A (vgl. Abbildung 1). Die zum Wort pp gehörende Schienenanlage ist aber nicht sinnvoll.

Begründen Sie im Sachzusammenhang, weshalb die zu pp gehörende Schienenanlage nicht sinnvoll ist.

Modifizieren Sie das Zustandsübergangsdiagramm in Abbildung 2 derart, dass der zugehörige deterministische endliche Automat genau die Wörter der Sprache $L_A$ außer dem Wort pp akzeptiert.