Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik GK · Nachtermin 2022

Aufgabenstellung: Erstlesewörter und Lesetexte

In der Grundschule lernen Kinder zu Beginn nur einfache Wörter („Erstlesewörter“) zu lesen. Ein Wort gilt als einfach, wenn seine Aussprache weitgehend der Schreibweise entspricht und es zudem nur aus wenigen Silben besteht. In der deutschen Sprachwissenschaft gibt es Regeln zum Aufbau einer Silbe; für diese Klausur werden sie folgendermaßen vereinfacht:

Eine Silbe enthält als Silbenkern einen Vokal (a, e, i, o oder u) oder eine Vokalkombination aus zwei Vokalen.

Vor und nach dem Silbenkern kann ein Konsonant oder können mehrere Konsonanten stehen. Mit Konsonanten sind in dieser Aufgabe alle Buchstaben des Alphabets außer den Vokalen gemeint, nämlich die folgenden:

b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z

Abbildung 1: Regeln für den Aufbau einer Silbe

Der Einfachheit halber sind alle Wörter ausschließlich in Kleinbuchstaben notiert.

Wie schwer ein Text zu lesen ist, hängt neben der Silbenanzahl auch von der Buchstabenanzahl je Wort ab: Das Wort „Schifffahrt“ mit 11 Buchstaben ist schwerer zu lesen als das Wort „Nase“ mit 4 Buchstaben.

Lesetexte sollen mithilfe einer Software untersucht werden, die feststellt, ob deren Wörter für Erstleserinnen und Erstleser geeignet sind. Die Software entfernt vor der Prüfung zunächst alle Satzzeichen.

Dabei wird folgende Modellierung zugrunde gelegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lesetext

Objekte der Klasse Lesetext modellieren Lesetexte, die auf ihre Eignung als Erstlesetext untersucht werden können.

Auszug aus der Dokumentation der Klasse Lesetext

Lesetext(List<Wort> pWoerter) · Ein Objekt wird mit den Wörtern der Liste pWoerter initialisiert.

boolean istGeeignet() · Die Anfrage liefert den Wert true, wenn das Objekt als Erstlesetext geeignet ist, sonst liefert sie den Wert false.

List<Wort> gibWoerter() · Die Anfrage liefert die Liste aller Objekte der Klasse Wort, die zusammen den Lesetext bilden.

Die Klasse Wort

Objekte der Klasse Wort modellieren Wörter, die auf ihre Eignung zur Verwendung in Erstlesetexten untersucht werden können.

Auszug aus der Dokumentation der Klasse Wort

Wort(List<String> pSilben) · Ein Objekt mit den Silben der Liste pSilben wird initialisiert.

int gibAnzahlSilben() · Die Anfrage liefert die Anzahl der Silben, aus denen das Wort besteht.

String gibZeichenkette() · Die Anfrage liefert die zum Wort gehörige Zeichenkette.

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.

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.

Viele Silben in deutschen Texten haben nur einen Vokal. Es gibt aber auch Silben mit mehr als einem Vokal, weil es einige typische Vokalkombinationen gibt, wie z. B. ie im Wort viel oder au im Wort Maus.

Der in Abbildung 2 abgebildete Übergangsgraph des endlichen Automaten A über dem Eingabealphabet aller Vokale erkennt die am meisten verwendeten Vokale und Vokalkombinationen in Silben deutscher Wörter.

Teilaufgabe b)

b.1)

Geben Sie für den Automaten A den Startzustand sowie die Menge seiner Endzustände an.

b.2)

Erläutern Sie, was der Zustand $q_2$ des Automaten A im Sachzusammenhang bedeutet.

b.3)

Erläutern Sie mithilfe des Übergangsgraphen in Abbildung 2, weshalb es sich beim Automaten A nicht um einen deterministischen endlichen Automaten (DEA) handelt.

b.4)

Entwickeln Sie den Übergangsgraphen eines deterministischen endlichen Automaten, dessen akzeptierte Sprache mit der des Automaten A übereinstimmt.

Teilaufgabe c)

Der Automat A soll so verändert werden, dass der veränderte Automat weitere besonders geeignete Erstlesewörter erkennt. Dabei handelt es sich um zweisilbige Wörter der deutschen Sprache wie leiter, tiger oder fangen, für die Folgendes gilt:

1. Die erste Silbe beginnt mit einem Konsonanten, dann folgt ein Vokal bzw. eine Vokalkombination, und danach kann noch maximal ein Konsonant folgen.

2. Die zweite Silbe beginnt mit einem Konsonanten, dann folgt ein Vokal (keine Vokalkombination) und dann ein weiterer Konsonant.

Abbildung 3: Bedingungen für geeignete zweisilbige Erstlesewörter

Da unterschiedliche Konsonanten für die Beurteilung dieses Kriteriums keine Rolle spielen, werden alle Konsonanten der zu untersuchenden Wörter vor der Beurteilung durch den Automaten durch das Zeichen # ersetzt.

Beispiel: tiger wird zu #i#e#

c.1)

Modifizieren und erweitern Sie den Übergangsgraphen des Automaten A derart, dass der neue endliche Automat genau diejenigen vereinfachten Zeichenketten deutscher zweisilbiger Wörter akzeptiert, welche die Bedingungen aus Abbildung 3 erfüllen.

c.2)

Erläutern Sie, auf welche Weise Ihr endlicher Automat die Bedingungen umsetzt.