Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · Abitur NRW Informatik LK · Nachtermin 2023

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker jedes Jahr dieselbe Pflanzenart kultiviert, entzieht sie dem Boden fortwährend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten benötigen besonders viele Nährstoffe aus dem Boden und gelten deshalb als stark zehrend.

Ein zu starkes Auszehren des Bodens kann verhindert werden, indem die zeitliche Abfolge der auf einem Acker angebauten Pflanzenarten klug festgelegt wird. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden hier vier Gruppen unterschieden:

wenig zehrende Pflanzenarten (w),

mittel zehrende Pflanzenarten (m),

stark zehrende Pflanzenarten (s) und

Zwischenfrüchte (z).

Zwischenfrüchte sind Pflanzenarten, die vor allem der Erholung des Bodens dienen.

Automaten sollen überprüfen, ob eine geplante Fruchtfolge vereinfachten landwirtschaftlichen Regeln genügt. Fruchtfolgen werden hierfür als Zeichenketten notiert. So bedeutet die Zeichenkette smz, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Abbildung 1 zeigt das Zustandsübergangsdiagramm eines solchen deterministischen endlichen Automaten A. Als Eingabewort erhält er eine Zeichenkette, die eine Fruchtfolge darstellt. Er akzeptiert genau die Zeichenketten der Fruchtfolgen, nach denen der Acker in der nächsten Anbauperiode für jede beliebige Pflanzengruppe bereit ist. Übergänge, die nicht eingezeichnet sind, führen in einen Fehlerzustand.

Der Boden kann auch durch sogenannte Mischkulturen fruchtbar gehalten werden. Hierbei wird der Acker in Reihen aufgeteilt, wobei jede Reihe nur mit einer Pflanzenart bestellt wird. Nebeneinanderliegende Reihen erhalten Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, dagegen schlecht neben Rote Bete. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art aneinandergrenzen.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

Ein Objekt der Klasse Pflanzenart modelliert eine Pflanzenart für die Ackerplanung.

Signatur / Konstruktor / Methode · Beschreibung

Pflanzenart(String pName) · Ein Objekt der Klasse mit dem Pflanzenart-Namen pName wird initialisiert.

String gibName() · Die Methode liefert den Namen der Pflanzenart.

List<Pflanzenart> gibGuteNachbarn() · Die Methode liefert eine Kopie der Liste aller Pflanzenarten, die gut neben der eigenen Pflanzenart gepflanzt werden können.

void fuegeGutenNachbarnZu(Pflanzenart pPflanzenart) · Die Pflanzenart pPflanzenart wird an die Liste der guten Nachbarpflanzenarten angehängt. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

Die Klasse Ackerplanung

Ein Objekt der Klasse Ackerplanung verwaltet Pflanzenarten für die Ackerplanung.

Signatur / Konstruktor / Methode · Beschreibung

Ackerplanung() · Ein neues Objekt wird initialisiert. Es werden zu Beginn noch keine Pflanzenarten verwaltet.

List<Pflanzenart> gibAllePflanzenarten() · Die Methode liefert eine Liste mit allen verwalteten Pflanzenarten.

void fuegePflanzenartZu(Pflanzenart pPflanzenart) · Die Methode hängt das Objekt pPflanzenart an die Liste der verwalteten Pflanzenarten allePflanzenarten an. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

List<Pflanzenart> passtZwischen(Pflanzenart pPflanzenart1, Pflanzenart pPflanzenart2) · Die Methode liefert eine Liste mit Pflanzenarten, die aufgrund von landwirtschaftlichen Kriterien zwischen die beiden Pflanzenarten pPflanzenart1 und pPflanzenart2 gepflanzt werden können.

Die generische Klasse List<ContentType>

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.

Signatur · Beschreibung

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

Die Klasse String (Ausschnitt)

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Signatur · Beschreibung

char charAt(int index) · Die Methode liefert das Zeichen an dem angegebenen Index index. Der Index reicht von 0 einschließlich bis zur length() - 1. Das erste Zeichen besitzt den Index 0, das nächste den Index 1 und so weiter.

int compareTo(String anotherString) · Die Methode vergleicht zwei Zeichenketten lexikografisch. Sie liefert einen Integerwert kleiner als 0, wenn der String lexikografisch vor der übergebenen Zeichenkette anotherString anzuordnen ist. Sie liefert einen Integerwert größer als 0, wenn der String lexikografisch nach der übergebenen Zeichenkette anotherString anzuordnen ist. Sind beide Zeichenketten identisch, wird der Wert 0 zurückgegeben.

boolean equals(Object anObject) · Die Methode liefert genau dann true, wenn der anObject nicht null ist und wenn das übergebene Objekt anObject vom Typ String ist und die gleiche Zeichenkette repräsentiert.

int indexOf(String str) · Die Methode liefert den Index des ersten Zeichens beim ersten Vorkommen der übergebenen Zeichenkette str. Kommt die übergebene Zeichenkette nicht vor, wird -1 zurückgegeben.

int length() · Die Methode liefert die Länge der Zeichenkette.

boolean startsWith(String prefix) · Die Methode liefert genau dann den Wert true, wenn die Zeichenkette mit dem angegebenen Präfix prefix beginnt. Andernfalls liefert sie den Wert false. Wird eine leere Zeichenkette oder die identische Zeichenkette übergeben, liefert die Methode dementsprechend ebenfalls den Wert true.

String substring(int beginIndex) · Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Ende der Zeichenkette. Der Wert des Parameters beginIndex darf nicht größer als die Länge der Zeichenkette sein. Ist er gleich der Länge der Zeichenkette, so wird die leere Zeichenkette "" zurückgegeben.

String substring(int beginIndex, int endIndex) · Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Index endIndex - 1 der Zeichenkette. Der Wert des Parameters endIndex darf nicht größer als die Länge des Strings sein. Der Wert des Parameters beginIndex muss größer oder gleich 0 sein und darf nicht größer als der Wert von endIndex sein. Sind beide Werte der Parameter identisch, so wird die leere Zeichenkette "" zurückgegeben.

Teilaufgabe d) (3 + 4 + 2 + 5 Punkte)

Mit der unten angegebenen Grammatik $G$ lassen sich Mischkulturen aus den drei Pflanzenarten Buschbohne (b), Rote Bete (r) und Kartoffel (k) erzeugen. So steht die Zeichenkette rbkbrr für eine Mischkultur, in der zuerst eine Reihe Rote Bete, anschließend eine Reihe Buschbohnen, dann eine Reihe Kartoffeln, als vierte Reihe wieder Buschbohnen und zum Schluss zwei Reihen Rote Bete angebaut werden.

Startsymbol:

S

Terminalsymbole:

{b, r, k}

Nichtterminalsymbole:

{S, A, B}

Produktionen:

{ S → AB,

A → BbA | &epsilon;,

B → k | r | rr | &epsilon; }

d.1)

Zeigen Sie, dass rbkbrr zu der Sprache $L_G$ gehört, die von $G$ erzeugt wird.

d.2)

Beschreiben Sie im Sachzusammenhang, in welcher Weise die Pflanzenreihen jener Mischkulturen aufeinanderfolgen, deren Wörter in der Sprache $L_G$ liegen.

d.3)

Begründen Sie, weshalb $G$ keine reguläre Grammatik ist.

d.4)

Entwickeln Sie eine reguläre Grammatik, die die Sprache $L_G$ erzeugt.

Teilaufgabe e) (4 + 4 Punkte)

Eine neue Mischkultur mit zunächst unbekannter Reihenanzahl soll aus Buschbohnen (b), Rote Bete (r) und Kartoffeln (k) angelegt werden. Dafür existieren zwei Vorschläge zur Anordnung:

(1) Es wird einmal oder mehrmals die folgende Folge von vier Reihen nebeneinander gepflanzt: Kartoffel, Buschbohne, Rote Bete, Buschbohne.

Beispiel: kbrbkbrb

(2) Es kommen zunächst mindestens zwei Reihen Kartoffeln, dann eine Reihe Buschbohnen und dann die entsprechende Anzahl an Rote-Bete-Reihen. Insgesamt sind es genauso viele Reihen Kartoffeln wie Rote Bete.

Beispiel: kkkkbrrrr

Die Zeichenkette der geplanten Mischkultur dient als Eingabewort für einen endlichen Automaten.

e.1)

Beurteilen Sie, ob ein endlicher Automat mit dem Eingabealphabet {k, r, b} existiert, der feststellen kann, ob ein Eingabewort einer Mischkultur der Form (1) entspricht.

e.2)

Erläutern Sie, wie ein Kellerautomat mit dem Eingabealphabet {k, r, b} arbeitet, der ein Eingabewort genau dann akzeptiert, wenn es einer Mischkultur der Form (2) entspricht.