Aufgabe 4 - Grammatiken und Kellerautomaten · Abitur NRW Informatik LK · Nachtermin 2022

Thema: Grammatiken, Kellerautomaten und Grenzen endlicher Automaten · Aus der Prüfung LK · Nachtermin (2022)

Aufgabenstellung

Aufgabenstellung:

In der Grundschule lernen Kinder anfangs nur das Lesen einfacher Wörter („Erstlesewörter“). Ein Wort gilt als einfach, wenn seine Aussprache weitgehend dem Schriftbild entspricht und es nur aus wenigen Silben besteht. Die deutsche Sprachwissenschaft kennt Regeln für den Aufbau von Silben; für diese Klausur werden sie folgendermaßen vereinfacht:

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

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

Bestimmen Sie zwei Eigenschaften, die den Aufbau der Wörter beschreiben und die auf sämtliche mit der Grammatik $G_1$ ableitbaren Wörter zutreffen.

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

Wörter mit vielen Konsonanten lassen sich schlecht lesen. Als geeignet für Erstlesetexte gelten Wörter, die höchstens doppelt so viele Konsonanten wie Vokale enthalten.

Weil es hier nicht auf die einzelnen Konsonanten und Vokale ankommt, wird im Eingabewort vor der Prüfung durch den Kellerautomaten jeder Konsonant durch das Zeichen b und jeder Vokal durch das Zeichen a ersetzt.

Entwickeln Sie einen nichtdeterministischen Kellerautomaten, der prüft, ob ein Eingabewort höchstens doppelt so viele b wie a enthält.

Stellen Sie dar, wie das Wort babab erkannt wird.

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

Beurteilen Sie, ob ein endlicher Automat existiert, der entscheidet, ob ein Eingabewort höchstens fünf Zeichen umfasst.

Aufgabenstellung: Aufgabe 4 - Grammatiken und Kellerautomaten · Abitur NRW Informatik LK · Nachtermin 2022

Lösung

Nach den offiziellen Korrekturhinweisen

Ermitteln Sie drei Wörter, die sich mithilfe der Grammatik G1 ableiten lassen.

Lösung: man / ton / wal / mal / mas / wen / wes / tal / tan / tul / tun

Bestimmen Sie zwei Eigenschaften, die den Aufbau der Wörter beschreiben und die auf sämtliche mit der Grammatik G1 ableitbaren Wörter zutreffen.

Lösung: Alle Wörter haben die Länge 3; alle Wörter beginnen und enden mit einem Konsonanten (bzw. haben genau einen Vokal in der Mitte).

Entwerfen Sie die reguläre Grammatik G2, die die Grammatik G1 so erweitert, dass auch die Wörter weg und tag erzeugt werden.

Lösung: N_2 = N_1 \cup \{G\}, T_2 = T_1 \cup \{g\}, P_2 = P_1 \cup \{G \rightarrow g, T \rightarrow aG, W \rightarrow eG\}

Stellen Sie dar, wie das Wort babab erkannt wird.

Lösung: | Zustand | Kellerinhalt | Gelesenes Eingabesymbol | Neuer Kellerinhalt | Neuer Zustand | | :---: | :---: | :---: | :---: | :---: | | $q_0$ | $\#$ | b | $B\#$ | $q_1$ | | $q_1$ | B | a | $\#$ | $q_2$ | | $q_2$ | $\#$ | $\varepsilon$ | $A\#$ | $q_1$ | | $q_1$ | A | b | $\#$ | $q_1$ | | $q_1$ | $\#$ | a | $AA\#$ | $q_1$ | | $q_1$ | A | b | $A\#$ | $q_1$ | | $q_1$ | A | $\varepsilon$ | $\varepsilon$ | $q_3$ |

Beurteilen Sie, ob ein endlicher Automat existiert, der entscheidet, ob ein Eingabewort höchstens fünf Zeichen umfasst.

Lösung: Ja, ein solcher endlicher Automat existiert.

c) Stellen Sie dar, wie das Wort babab erkannt wird.

Lösung: (z0, babab, #) -> (z0, abab, B#) -> (z0, bab, #) -> (z0, ab, B#) -> (z0, b, #) -> (ze, ε, #)

e) Beurteilen Sie, ob ein endlicher Automat existiert, der entscheidet, ob ein Eingabewort höchstens fünf Zeichen umfasst.

Lösung: Ja, das ist möglich. Ein endlicher Automat kann dies mit 7 Zuständen (Startzustand q0 für 0 Zeichen bis q5 für 5 Zeichen als akzeptierende Zustände sowie einem Fangzustand q6 für Wörter ab 6 Zeichen) modellieren.

Entwickeln Sie einen nichtdeterministischen Kellerautomaten, der prüft, ob ein Eingabewort höchstens doppelt so viele b wie a enthält.

Lösung: Zustandsmenge: $\{q_0, q_1, q_2, q_3\}$ Eingabealphabet: $\{a, b\}$ Kelleralphabet: $\{A, B, \#\}$ Anfangszustand: $q_0$ Kellerstartsymbol: $\#$ Menge der Endzustände: $\{q_3\}$

Die ausführliche Erklärung Schritt für Schritt (mit KI) gibt es mit Premium. Premium

Löse sie direkt hier: automatische Korrektur, Hinweise und Lösung Schritt für Schritt.

‹ Aufgabe 4 - Grammatiken und Kellerautomaten · LK · Haupttermin 2022 · Aufgabe 4 - Grammatiken, Kellerautomaten und Gren… · GK · Haupttermin 2021 ›

Aufgabe 4 - Grammatiken und Kellerautomaten · Abitur NRW Informatik LK · Nachtermin 2022

Aufgabenstellung

Lösung

Mehr Aufgaben zu Grammatiken, Kellerautomaten und Grenzen endlicher Automaten