26.4 Abituraufgaben

Abitur 2017

Beginnen wir mit der letzten Abituraufgabe zum Thema Automaten und Sprachen, nämlich der Aufgabe aus dem Jahre 2017.

In dieser Aufgabe ging es um ein Handyspiel mit einem schachbrettartigem Spielfeld, auf dem Edelsteine liegen, ungefähr so:

Ausschnitt aus dem Spielfeld mit dem Startfeld (grün)

In der Abituraufgabe war das Spielfeld natürlich nicht so schön dargestellt wie hier.

Eine Spielfigur kann nun über das Spielfeld wandern, muss dabei allerdings ein paar Regeln beachten:

• Die Figur darf nur nach Norden, nach Westen oder nach Südosten gehen.
• Auf den grauen Feldern kann die Figur einen Edelstein einsammeln,
• auf den weißen Feldern kann sie beliebig viele Edelsteine ablegen.
• Die Figur kann immer nur einen Stein gleichzeitig tragen.

Wenn die Figur einen Stein auf einem weißen Feld ablegt, sinkt dieser sofort nach unten, so dass das weiße Feld wieder leer ist. Allerdings erhält der Spieler einen Geldbetrag für jeden abgelegten Edelstein.

Die Situation nach einigen Spielzügen

Hier ist die Spielfigur (blauer Kreis) zunächst nach Norden gegangen und hat den Edelstein des Startfeldes auf das angrenzende weiße Feld gelegt. Dann ist er nochmal nach Norden gegangen und hat den Edelstein des grauen Feldes aufgenommen. Nun ist er nach Westen gegangen und hat den Edelstein auf das weiße Feld abgelegt. Dann ist er wieder nach Norden gegangen, hat den Edelstein aufgenommen und auf das angrenzende westliche Feld gelegt. Dort steht die Spielfigur im Augenblick und überlegt, wie es weitergeht...

Teilaufgabe a)

Nun zur ersten Teilaufgabe. Die Mitarbeiterin einer Softwarefirma hat den Auftrag, einen endlichen Automaten zu entwerfen, der prüft, ob eine Folge von Spielzügen (zum Beispiel wie in der Abbildung oben) gültig ist.

Auf der Seite 2 der Abituraufgabe wird den Schülern und den wenigen Schülerinnen in der Abbildung 3 der Übergangsgraph eines DEAs gezeigt, den die Mitarbeiterin entworfen hat. Aus Copyrightgründen und um mir selbst und meinen Kollegen nicht mögliche Klausuraufgaben zu verbauen, wird dieser Graph jetzt nicht gezeigt.

Die Schüler sollen jetzt diesen Graphen beschreiben, also den Startzustand, das Eingabealphabet, die Menge der Zustände / Endzustände angeben. Dann sollen sie mit Hilfe des Automaten prüfen, ob die "Worte"

Nord - West - Sammeln - West - Nord - Ablegen

Sammeln - Nord - Südost - Ablegen - West - West

zur Sprache dieses Automaten gehören.

Wie können das sofort ohne Kenntnis der Übergangsfunktion graphisch überprüfen, indem wir die Spielzüge simulieren:

Ein "Wort"

Wie man sofort sieht, ist das Wort

Nord - West - Sammeln - West - Nord - Ablegen

ungültig bzw. gehört nicht zur Sprache des Automaten. Auf den grauen Feldern darf kein Stein abgelegt werden.

Das andere "Wort"

Das Wort

Sammeln - Nord - Südost - Ablegen - West - West

ist dagegen gültig und gehört zur Sprache des Automaten.

Außerdem sollen die S. in der Teilaufgabe a) die Bedeutung von zwei Zuständen herausarbeiten und begründen, wieso nur Wörter akzeptiert werden, bei denen die Summe Nord + West eine ungerade Zahl ist.

Teilaufgabe b)

In dieser Teilaufgabe sollen die S. eine reguläre Grammatik entwerfen, die zum oben beschriebenen DEA äquivalent ist. Anschließend sollen die S. entscheiden, ob zwei vorgegebene Wörter zu der Sprache dieser Grammatik gehören.

Teilaufgabe c)

Den S. wird eine Grammatik G1 vorgegeben, die ähnlich ist wie die Grammatik in Teilaufgabe b). Das Startsymbol, die Terminale und Nichtterminale sowie die Produktionsregeln werden auf Seite 3 der Aufgabe gezeigt. Zusätzlich wird den S. eine alternative Grammatik G2 gegeben, die ähnliche Produktionsregeln aufweist wie G1.

Die S. müssen dann begründen, wieso die Grammatik G1 nicht regulär ist, sie sollen alle Wörter angeben, die aus G1 erzeugt werden können und die aus genau drei Zeichen bestehen, und sie sollen darstellen, welche Zugfolgen mit Hilfe von G1 erzeugt werden können.

Dann sollen die S. eine linkslineare Grammatik G3 erzeugen, welche dieselbe Sprache wie G2 hat.

Und schließlich sollen die S. entscheiden, ob G1 und G2 die gleiche Sprache haben.

Teilaufgabe d)

In dieser Teilaufgabe werden die Regeln des Spiels geringfügig erweitert, und die S. sollen beurteilen, ob ein DEA auch mit dieser Erweiterung fertig wird.

Teilaufgabe e)

Hier werden die Spielregeln erheblich erweitert, indem mehr graue Felder eingeführt werden, auf denen Steine liegen können. Die S. sollen einen Übergangsgraphen eines DEA entwickeln, der zu den neuen Regeln passt.

Es tut mir leid, wenn ich mich hier manchmal etwas schwammig ausdrücke, aber ich will / darf ja nicht die komplette Aufgabenstellung hier präsentieren, vielleicht setze ich diese Aufgabe mal selbst als Klausuraufgabe ein, oder Kollegen von mir wollen das machen. Aber jedenfalls geben die Ausführungen auf dieser Seite einen guten Einblick in die Konstruktion künftiger Abituraufgaben, und jeder Schüler, der Informatik als Abiturfach wählt, ist gut beraten, sich intensiv mit endlichen Automaten und Grammatiken zu beschäftigen.