FH Graubünden PH Graubünden

Grammatiken

Algorithmisches Denken in der Primarschule

Zusammenfassung

Wie bereits in der Unterrichtseinheit «Formale Sprache 1» erwähnt, dreht sich ein wesentlicher Teil der Informatik um das Identifizieren von Mustern bzw. das Finden von Strukturen in Daten. In diesem Zusammenhang haben wir bereits die regulären Ausdrücke bzw. die endlichen Automaten kennengelernt. In dieser Unterrichtseinheit betrachten wir eine weitere Möglichkeit, Texte mit einem festen, endlichen Regelsystem zu generieren. Die erzeugenden Mechanismen sind hier sogenannte kontextfreie Grammatiken, die in der Informatik, beispielsweise bei Parsern und Compilern, eine wichtige Rolle spielen.

Kontextfreie Grammatiken generieren konktextfreie Sprachen, die eine echte Obermenge der regulären Sprachen sind, die wir mit endlichen Automaten beschreiben können. Die Idee ist hier, dass es zwei Typen von Symbolen gibt, mit denen Wörter «erzeugt» werden können. Die sogenannten Nichtterminale sind Symbole, die nach festen Regeln durch Sequenzen von Symbolen ersetzt werden können. Hingegen dürfen Terminale, der zweite Typ von Symbolen, nicht ersetzt werden. Die erzeugten Worte enthalten einzig Terminale.

In dieser Unterrichtseinheit werden unterschiedliche Grammatiken (wir verzichten hier auf das Adjektiv kontextfrei) vorgestellt, um Texte zu beschreiben. Es gibt hier diverse Aufgabentypen, die eine einfache Differenzierung ermöglichen.

Beispielsequenz

Wir betrachten folgende Regeln, um Worte (Sequenzen von Buchstaben) zu erzeugen. Auf ein weisses Blatt wird ein X geschrieben; anschliessend wird dieses X durch die drei Buchstaben 0X1 ersetzt. Danach werden die folgenden zwei Regeln beliebig oft angewendet:

Wir sind mit dem Prozess der Worterzeugung fertig, wenn kein X mehr in dem Wort vorkommt, also nur noch Nullen und Einsen aufgeschrieben sind.

Beispielsweise können wir das Wort 000111 mit den obigen Regeln erzeugen, indem wir Folgendes tun:

  1. Wir schreiben X auf das Blatt.
  2. Wir ersetzen dieses X durch 0X1.
  3. Wir ersetzen das X in der Mitte wieder durch 0X1 und erhalten so 00X11.
  4. Wir ersetzen das X in der Mitte erneut durch 0X1, sodass 000X111 entsteht.
  5. Am Ende löschen wir das X in der Mitte, damit nur noch 000111 übrig bleibt.

Diese fünf Schritte schreiben wir verkürzt als \[ X \Rightarrow 0X1 \Rightarrow 00X11 \Rightarrow 000X111 \Rightarrow 000111, \] wobei wir also vier Mal die erste und ein Mal die zweite Regel angewendet haben. Wenden wir die erste Regel sechs statt vier Mal an, erhalten wir hingegen \[ X \Rightarrow 0X1 \Rightarrow 00X11 \Rightarrow 000X111 \Rightarrow 0000X1111 \Rightarrow 00000X11111 \Rightarrow 0000011111. \] Wir sehen, dass die Wörter, die entstehen, immer aus einer festen Anzahl von Nullen bestehen, auf die genau dieselbe Anzahl Einsen folgt, also können die Worte 01, 0011, 000111, 00001111 etc. entstehen.

Aufgabe 1

Welche Wörter können mit den gegebenen Regeln nicht erzeugt werden? Ist es beispielsweise möglich, das Wort 011 zu erzeugen? Begründen Sie Ihre Aussage. Wir können die Regeln so modifizieren, dass die erzeugten Wörter mit einer festen Anzahl von Nullen beginnen, denen Einsen und Zweien folgen, wobei die Anzahl der Nullen der Anzahl der Einsen plus Zweien entspricht. Dies tun wir mit folgenden neuen Regeln:

Damit können wir beispielsweise \[ X \Rightarrow 0X1 \Rightarrow 00X21 \Rightarrow 000X221 \Rightarrow 0000X1221 \Rightarrow 00000X21221 \Rightarrow 0000021221 \] erzeugen.

Wir nennen X, 0, 1 und 2 Symbole und zusammen mit den Regeln sprechen wir von einer Grammatik. Die oben beschriebenen Regeln können wir vereinfacht darstellen, indem wir einen Pfeil verwenden. Wir entscheiden uns für die Regeln für «\to» statt «\Rightarrow»; so bedeutet X \to 0X1, dass X durch 0X1 ersetzt werden darf. Wenn wir das Löschen eines Symbols durch ein X markieren, ergeben sich für die obige Grammatik folgende Regeln: \[ X\to 0X1, X \to 0X2 \text{und} X \to \times\;. \]

Aufgabe 2

Modifizieren Sie die Regeln so, dass nur Wörter erzeugt werden können, die mit einer Anzahl von Nullen beginnen und anschliessend doppelt so viele Einsen enthalten, also zum Beispiel 000111111. Für jede Null am Anfang gibt es also zwei Einsen am Ende.

Verwenden Sie hierzu die soeben beschriebene Darstellung.

Aufgabe 3

Ein Palindrom ist ein Wort, das vorwärts und rückwärts gelesen gleich ist, zum Beispiel «Otto» oder «Hannah». Eine Palindromzahl ist wiederum eine Zahl, die vorwärts und rückwärts gelesen denselben Wert besitzt, zum Beispiel «171» oder «6233443326»; auch «5» ist eine Palindromzahl. Wir nehmen vereinfacht an, dass die Zahlen auch mit einer Null beginnen dürfen, also zum Beispiel «01177110».

Erstellen Sie eine Grammatik, mit der alle Palindromzahlen erzeugt werden können. Nebst Buchstaben und Zahlen können Symbole auch ganze Wörter sein. Ausserdem können wir verschiedene Symbole, die ersetzt werden dürfen, definieren – wir entscheiden uns hier für X, Y und Z als Bezeichnung für diese Symbole. Beginnen tun wir immer damit, dass ein X aufgeschrieben wird. Dann können wir zum Beispiel Sätze bilden mit den Regeln \begin{align*} X & \to \text{Urs isst} Y \\ Y & \to \text{sehr,} Y \\ Y & \to \text{sehr gerne Eis.} \end{align*} Durch die Anwendung dieser Regeln können die Sätze

Urs isst sehr gerne Eis.

oder auch

Urs isst sehr, sehr, sehr gerne Eis.

erzeugt werden. Auch können mehrere ersetzbare Symbole gleichzeitig in einer Regel verwendet werden, zum Beispiel können wir mit \begin{align*} X & \to Y \text{isst} Z \\ Y & \to \text{Stefania}\\ Y & \to \text{Urs}\\ Z & \to \text{sehr,} Z \\ Z & \to \text{sehr gerne Eis.} \end{align*} alle obigen Sätze mit Urs erzeugen, aber auch noch beispielsweise

Stefania isst sehr, sehr, sehr, sehr gerne Eis.

Aufgabe 4

Philippa isst (sehr, sehr, ...) sehr gerne Mandeln und Heidi isst (sehr, sehr, ...) sehr gerne Nüsse. Kannst du eine Grammatik erstellen, mit der diese beiden Sachverhalte als Sätze formuliert werden können?

Verwenden Sie hierzu wieder wie oben ersetzbare Symbole X, Y und Z.

Thomas' liebstes Hobby ist Schlafen, aber leider schafft er es nicht immer, genug Schlaf zu kriegen. Konkret gilt Folgendes:

Wenn Thomas sehr wenig schläft, ist er danach sehr müde.
Wenn Thomas sehr, sehr wenig schläft, ist er danach sehr, sehr müde.
Wenn Thomas sehr, sehr, sehr wenig schläft, ist er danach sehr, sehr, sehr müde.

Dabei ist darauf zu achten, dass die Anzahl der «sehr» am Anfang und am Ende identisch sein müssen – sonst stimmt die Aussage nicht. Thomas möchte Regeln erstellen, die dies beschreiben und macht folgenden Vorschlag: \begin{align*} X & \to \text{Wenn Thomas} Y \text{sehr wenig schläft, ist er danach} Y \text{sehr müde.}\\ Y & \to \text{sehr,} Y \\ Y & \to \times \end{align*}

Aufgabe 5

Die obigen Regeln sind leider nicht korrekt, denn sie erlauben es, Sätze zu erzeugen, die nicht dem beschriebenen Format entsprechen. Erklären Sie, welche Sätze dies sind und beschreiben Sie, wo das Problem liegt.

Aufgabe 6

Erstellen Sie neue Regeln, mit denen die korrekten Sätze für Thomas erzeugt werden können.

Lösungen zu den Aufgaben

Aufgabe 1

Das Wort 011 kann nicht erzeugt werden, da keine Eins geschrieben werden kann, ohne gleichzeitig eine Null zu schreiben. Es wird mit den angegebenen Regeln also immer dieselbe Anzahl Nullen und Einsen erzeugt.

Aufgabe 2

Die Regeln können einfach abgeändert werden, sodass mit jeder Null am Anfang eines Wortes die doppelte Anzahl Einsen am Ende des Wortes erzeugt wird: \[ X\to 0X11 \text{und} X \to \times\;. \]

Aufgabe 3

Palindromzahlen lassen sich mit folgenden Regeln erzeugen: \begin{align*} X &\to 0X0, X \to 1X1, X \to 2X2, X \to 3X3\\ X &\to 4X4, X \to 5X5, X \to 6X6, X \to 7X7\\ X &\to 8X8, X \to 9X9, \\ X & \to 0, X \to 1, X \to 2, X \to 2\\ X & \to 3, X \to 4, X \to 5, X \to 6\\ X & \to 7, X \to 8, X \to 9, X \to \times \end{align*} Hierbei wird die Zahl mit den ersten zehn Regeln von «vorne und hinten gleichzeitig» aufgebaut. Am Ende kann dann das X mit einer der letzten elf Regeln durch eine einzelne Ziffer ersetzt oder gelöscht werden.

Aufgabe 4

Hier müssen wir die Regeln so gestalten, dass nur die Kombinationen Philippa und Mandeln bzw. Heidi und Nüsse möglich sind. Wir stellen dies mit den ersten zwei Regeln sicher: \begin{align*} X & \to \text{Philippa isst} Y \text{sehr gerne Mandeln.}\\ X & \to \text{Heidi isst} Y \text{sehr gerne Nüsse.}\\ Y & \to \text{sehr,} Y \\ Y & \to \times \end{align*} Wir erlauben also, auf zwei Arten zu starten und beliebig viele «sehr,» einzufügen. Damit am Ende kein Y übrig bleibt, kann das letzte Y gelöscht werden.

Aufgabe 5

Das Problem mit den gezeigten Regeln ist, dass die Anzahl der «sehr» am Anfang und Ende nicht unbedingt gleich sein muss. Beispielsweise kann der Satz

Wenn Thomas sehr, sehr, sehr wenig schläft, ist er danach sehr, sehr müde.

mit \begin{align*} X & \Rightarrow \text{Wenn Thomas} Y \text{sehr wenig schläft, ist er danach} Y \text{sehr müde.} \\ & \Rightarrow \text{Wenn Thomas sehr,} Y \text{sehr wenig schläft, ist er danach} Y \text{sehr müde.} \\ & \Rightarrow \text{Wenn Thomas sehr, sehr,} Y \text{sehr wenig schläft, ist er danach} Y \text{sehr müde.} \\ & \Rightarrow \text{Wenn Thomas sehr, sehr, sehr wenig schläft, ist er danach} Y \text{sehr müde.} \\ & \Rightarrow \text{Wenn Thomas sehr, sehr, sehr wenig schläft, ist er danach sehr,} Y \text{sehr müde.} \\ & \Rightarrow \text{Wenn Thomas sehr, sehr, sehr wenig schläft, ist er danach sehr, sehr müde.} \end{align*} erzeugt werden. Das erste Y kann beliebig oft durch «sehr, Y» ersetzt werden und das zweite Y unabhängig davon. Es lassen sich also am Anfang und Ende eine ungleiche Anzahl von «sehr,» einfügen.

Aufgabe 6

Die Lösung ist, die «sehr» am Anfang und Ende gleichzeitig zu erzeugen. Erst nachdem dies geschehen ist, wird der Mittelteil erzeugt. Wir können dies mit folgenden Regeln erzielen: \begin{align*} X & \to \text{Wenn Thomas} Y \text{sehr müde.} \\ Y & \to \text{sehr,} Y \text{sehr,}\\ Y & \to \text{sehr wenig schläft, ist er danach}\\ \end{align*}

Didaktischer Kommentar

Grammatiken ermöglichen uns, wie auch endliche Automaten aus der Unterrichtseinheit «Formale Sprachen 1», Daten zu erzeugen, die eine bestimmte Struktur besitzen. Auch hier wird ein endliches System, die Regeln, verwendet, um eine potenziell unendlich grosse Menge an Informationen endlich codieren zu können.

Sicherlich ist es schwerer, eine Intuition für Grammatiken zu entwickeln, als für endliche Automaten. Es ist deswegen dringend empfohlen, die Unterrichtseinheit «Formale Sprachen 1» vor dieser zu behandeln.

Grammatiken kommen in der Praxis in allen möglichen Anwendungen vor, wenn es darum geht, für den Computer lesbare Sprachen auf Fehler zu überprüfen, also zum Beispiel bei Mark-Down-Sprachen wie HTML oder Programmiersprachen.

Die Unterrichtseinheit enthält die folgenden Aspekte des algorithmischen Denkens.

Quellenangaben und weiterführende Literatur

  1. Hans-Joachim Böckenhauer und Juraj Hromkovič. Formale Sprachen. Endliche Automaten, Grammatiken, lexikalische und syntaktische Analyse. Springer Vieweg, 2012.
  2. Kontextfreie Grammatiken: Wikipedia – Die freie Enzyklopädie. https://de.wikipedia.org/wiki/Kontextfreie_Grammatik

Zurück PDF Übungen als PDF