Aufgabe 4 - Endliche Automaten · 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.

a)

Geben Sie ein Wort von möglichst geringer Länge an, in dem alle Pflanzengruppen vorkommen und das der Automat A akzeptiert.

Erläutern Sie im Sachzusammenhang, welchen Bedingungen Fruchtfolgen genügen müssen, damit die zugehörigen Zeichenketten vom Automaten A akzeptiert werden.

b)

Weil Zwischenfrüchte die Erträge der folgenden Pflanzen erhöhen, sollen die Regeln für Fruchtfolgen angepasst werden. Das Zustandsübergangsdiagramm des Automaten A soll so erweitert werden, dass

unmittelbar vor jeder stark zehrenden Pflanzenart (s) eine Zwischenfrucht (z) in der Fruchtfolge steht.

Außerdem soll die Fruchtfolge mit einer Zwischenfrucht (z) enden.

Abgesehen von diesen Einschränkungen soll der neue Automat genau die Wörter akzeptieren, die auch der Automat A akzeptiert (vgl. Abbildung 1).

Modifizieren Sie das Zustandsübergangsdiagramm des Automaten A gemäß der beschriebenen Erweiterung.

Zeigen Sie, dass Ihr Automat zswz akzeptiert, sz hingegen nicht.