Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · Abitur NRW Informatik GK · Nachtermin 2023

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker Jahr für Jahr dieselbe Pflanzenart kultiviert, verliert der Boden fortlaufend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten beanspruchen besonders viele Nährstoffe und heißen deshalb stark zehrend.

Einer zu starken Auszehrung des Bodens beugt man vor, indem man die Abfolge der angebauten Pflanzenarten auf einem Acker klug festlegt. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden nachfolgend 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 vereinfachte landwirtschaftliche Regeln einhält. Dazu werden Fruchtfolgen als Zeichenketten notiert. Die Zeichenkette smz steht zum Beispiel dafür, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Der Boden lässt sich auch durch sogenannte Mischkulturen fruchtbar halten. Hierbei wird der Acker in Reihen unterteilt, und jede Reihe erhält genau eine Pflanzenart. In benachbarten Reihen stehen Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, neben Rote Bete dagegen ungünstig. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art direkt nebeneinander liegen.

Zur Planung einer Mischkultur wird ein Programm entworfen, dem die folgende Teilmodellierung zugrunde liegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

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

Dokumentation der Klasse Pflanzenart

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> gibGutenNachbarn()

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.

boolean istGuterNachbar(Pflanzenart pPflanzenart)

Die Methode liefert true, wenn eine Pflanzenart mit demselben Namen wie pPflanzenart in der Liste der guten Nachbarpflanzenarten enthalten ist, ansonsten false.

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.

Die Klasse String

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

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

Mit der nachstehenden 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, die aus einer Reihe Rote Bete, gefolgt von einer Reihe Buschbohnen und einer Reihe Kartoffeln, dann einer vierten Reihe Buschbohnen und schließlich zwei Reihen Rote Bete besteht.

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 zur Sprache $L_G$ gehört, die von $G$ erzeugt wird. [3 Punkte]

d.2)

Beschreiben Sie im Sachzusammenhang, in welcher Weise die Pflanzenreihen von Mischkulturen angeordnet sind, die durch Wörter der Sprache $L_G$ dargestellt werden. [4 Punkte]

d.3)

Begründen Sie, weshalb $G$ keine reguläre Grammatik ist. [2 Punkte]

d.4)

Entwickeln Sie eine reguläre Grammatik, die die Sprache $L_G$ erzeugt. [5 Punkte]

Teilaufgabe e)

Eine Person plant, eine neue Mischkultur mit zunächst unbekannter Reihenanzahl aus Buschbohnen (b), Roter Bete (r) und Kartoffeln (k) anzulegen.

Für die Anlage einer solchen Mischkultur werden zwei Vorschläge gemacht:

(1) Die Reihenfolge Kartoffel, Buschbohne, Rote Bete, Buschbohne wird ein- oder mehrmals hintereinander gepflanzt.

Beispiel: kbrbkbrb

(2) Zuerst stehen mindestens zwei Reihen Kartoffeln, danach eine Reihe Buschbohnen und anschließend Reihen Rote Bete, und zwar ebenso viele wie Kartoffelreihen.

Beispiel: kkkkbrrrr

Die Zeichenkette der geplanten Mischkultur dient als Eingabewort eines endlichen Automaten.

e.1)

Beurteilen Sie, ob ein endlicher Automat mit dem Eingabealphabet {k, r, b} existiert, der entscheidet, ob ein Eingabewort eine Mischkultur der Form (1) darstellt. [4 Punkte]

e.2)

Begründen Sie, dass kein endlicher Automat existiert, der entscheiden kann, ob ein Eingabewort eine Mischkultur der Form (2) darstellt. [4 Punkte]