26.5 ältere Abituraufgaben

Abitur 2016

Hier soll ein DEA überprüfen, ob die Bestellungen in einer Pizzeria richtig eingegeben wurden. Dazu wird den Schülern die graphische Darstellung der Übergangsfunktion vorgegeben, die drei Endzustände sind hier durch doppelte Kreise markiert. Insgesamt hat der Automat fünf Zustände.

Die konkreten Aufgaben sahen wie folgt aus:

1. Die S. sollten ein Wort der Länge 7 und ein Wort mit minimaler Länge angeben, das vom Automaten als korrekt akzeptiert wird. Dann sollten die S. für zwei vorgegebene Worte die Abfolge der Zustände des DEAs angeben und entscheiden, ob die Worte zur Sprache des Automaten gehören.
2. In der zweiten Aufgabe sollten die S. das Eingabealphabet, die Menge der Zustände, den Startzustand und die Menge der Endzustände aus dem Diagramm entnehmen. Eine völlig simple Aufgabe, für die es sage und schreibe 10 Punkte gab. Für diese 10 Punkte sollten die S. allerdings auch die Bedeutung einiger spezieller Zustände erläutern.
3. In der dritten Teilaufgabe sollten die Kunden der Pizzeria unter bestimmten Bedingungen kostenlose Überraschungen ordern können. Dazu wurde den Schülern eine Grammatik G vorgegeben. Die S. sollten dann erläutern, wie sich der Bestellvorgang entsprechend der Grammatik von dem Bestellvorgang entsprechend dem Automaten unterscheidet. Außerdem sollten die S. erläutern, warum G nicht regulär ist, und dann eine tatsächlich reguläre Grammatik entwerfen, die das gleiche leistet wie G.
4. In der vierten Teilaufgabe sollten die Bestellmöglichkeiten erweitert werden. Dazu wurde den S. eine tabellarische Darstellung der ersten Übergangsfunktion vorgegeben. Die S. sollten dann erläutern, welcher Zusamenhang zwischen der graphischen Darstellung und der Tabelle besteht, anschließend sollten sie die Tabelle nach den Vorgaben erweitern.
5. In der fünften Teilaufgabe mussten die S. begründen, wieso ein DEA nicht zählen kann.

Aufgabe 2015

In dieser Aufgabe ging es um Kommentare, wie sie in Programmiersprachen üblich sind. Den Schülenr wurde ein Zustandsübergangsgraph (also die graphische Darstellung der Übergangsfunktion) eines entsprechenden DEA vorgegeben. Dieser DEA hatte wieder mal fünf Zustände, davon drei Endzustände. Das Eingabealphabet war S = {/, *, #, z}, wobei z für ein beliebiges Zeichen steht.

Die konkreten Aufgaben:

1. Die erste Aufgabe war ähnlich wie die von 2016: Überprüfen eines vorgegebenen Wortes sowie Angeben von Worten, welche vom Automaten akzeptiert werden.
2. Auch die zweite Aufgabe ähnelte der von 2016: Die Rolle von zwei bestimmten Zuständen erläutern.
3. In der dritten Aufgabe sollte die graphische Darstellung der Übergangsfunktion in eine tabellarische Darstellung überführt werden.
4. Die vierte Aufgabe bestand darin, den Automaten etwas zu erweitern.
5. Die fünfte Aufgabe bezog sich wieder auf Grammatiken. Den S. wurde eine Grammatik G vorgegeben, und die Aufgabe war dann, zu erläutern, welche Eigenschaft die von der Grammatik erzeugten Wörter haben. Außerdem sollten die S. begründen, warum die Grammatik nicht regulär ist, und sie sollten eine reguläre Grammatik mit der gleichen Sprache wie G erzeugen.

Aufgabe 2014

Hier ging es um die "Blasensprache", die von einem Kaugummihersteller zu Werbezwecken entwickelt worden ist. Auch in dieser Aufgabe wurde den Schülern die graphische Darstellung der Übergangsfunktion (4 Zustände) sowie das Eingabealphabet vorgegeben.

Die Aufgaben:

1. Und wieder musste gezeigt werden, dass zwei vorgegebene Worte vom Automaten akzeptiert werden. Dann sollte die Graphik in eine Tabelle umgewandelt werden. Am Ende der ersten Teilaufgabe sollte der DEA in eine Grammatik umgewandelt werden, deren Sprache aus genau den Worten besteht, die der Automat akzeptiert.
2. In der zweiten Teilaufgabe wird eine Vereinfachung des DEA vorgeschlagen. Die S. sollten diesen Vorschlag analysieren.
3. Die dritte Teilaufgabe war interessant. Hier wurde den S. der Java-Quelltext einer Methode vorgegeben, die Zufallstexte erzeugte, die ungefähr der Sprache des Automaten entsprachen. Die S. sollten diesen Quelltext analysieren und angeben, welche Ausgabe er unter den gegebenen Bedingungen erzeugt. Auch sollte der Zusammenhang zwischen dem Quelltext und dem DEA aufgezeigt werden.
4. In der vierten Teilaufgabe sollte der Automat von den S. modifiziert werden.
5. Die fünfte Teilaufgabe behandelte wieder eine Grammatik G, die ebenfalls "Blasensprache" erzeugt. Die S. sollten begründen, wieso diese Grammatik keine reguläre Grammatik ist, und sie sollten beschreiben, welche Worte von dieser Grammatik erzeugt werden können. Außerdem sollten die S. begründen, wieso es keinen DEA gibt, der die gleiche Sprache hat wie die Grammatik.

Diese kleine Auswahl von Aufgaben sollte genügen, um Ihnen zu zeigen, wie wichtig das Thema "Determinierte endliche Automaten" für das Zentralabitur in NRW ist und wie die Aufgaben in der Regel "gestrickt" sind.

Aufgabe 2012

Diese alte Abituraufgabe ist nach den schlimmen Waldbränden in Australien im Januar 2020 wieder ganz aktuell. Es geht um Waldbrände und vorbeugende Maßnahmen der Feuerwehr, um Waldbrände zu verhindern. Ausgangsmaterial für diese Aufgabe ist der folgende determinierte endliche Automat:

Der Waldbrand-DEA

Der Startzustand dieses Automaten ist 1, der Endzustand 4. Wenn der Automat im Endzustand angekommen ist, ist der Wald wirklich in Gefahr zu brennen oder er brennt sogar schon. Die Symbole sind folgendermaßen zu deuten:

• h = heiß und sonnig
• t = trocken (dabei muss es nicht unbedingt heiß sein)
• s = leichter Regen (Sprüh-, Nieselregen)
• r = starker Regen

Betrachten wir mal ein typisches Beispiel. Im Zustand 1 ist der Wald völlig ungefährdet. Nun ist es eine Tag Periode lang heiß (h). Der Wald gerät in den Zustand 3. Ist es noch eine weitere Periode lang heiß, gerät der Wald in den Zustand 4, was "höchste" Gefährdungsstufe mit einer sehr hohen Waldbrandgefahr bedeutet. Durch einen leichten Regen (s) gelangt der Wald wieder in die weniger gefährliche Stufe 3. Fällt weiterhin ein leichter Regen (s), gelangt der Wald in die Stufe 2, und mit noch mehr Regen (leicht oder stark ist jetzt egal) sogar in die Ausgangsstufe 1.