Aufgabe 4 - Grammatiken und Grenzen endlicher Aut… · 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.

a)

Ausgewählte Wörter für Leseanfänger werden von der folgenden regulären Grammatik $G_1 = (N_1, T_1, S_0, P_1)$ erzeugt.

Nichtterminale: $N_1 = \{S_0, L, M, N, S, T, W\}$

Terminale: $T_1 = \{a, e, l, m, n, o, s, t, u, w\}$

Startsymbol: $S_0$

Produktionen: $P_1 = \{ S_0 \to mM \mid tT \mid wW,$

$L \to l,$

$M \to aL \mid aN \mid uS,$

$N \to n,$

$S \to s,$

$T \to aL \mid oN \mid uN,$

$W \to aL \mid aS \mid eN$ }

Ermitteln Sie drei Wörter, die sich mit der Grammatik $G_1$ ableiten lassen.

= 3, incorrect: isAnswered && validWordsCount < 3 }"

autocomplete="off" autocapitalize="off" spellcheck="false" />

Bestimmen Sie zwei Eigenschaften, die beschreiben, wie die Wörter aufgebaut sind, und die für sämtliche mit der Grammatik $G_1$ ableitbaren Wörter gelten.

Entwerfen Sie die reguläre Grammatik $G_2$, die $G_1$ so erweitert, dass außerdem die Wörter weg und tag erzeugt werden.

e)

Der Praktikant vermutet, dass sich die Frage, ob ein Wort höchstens fünf Zeichen lang ist, nicht nur durch ein Programm, sondern auch durch einen endlichen Automaten beantworten lässt.

Begründen Sie, dass ein endlicher Automat existiert, der feststellt, ob ein Eingabewort höchstens fünf Zeichen enthält.