Gegeben ist diese Grammatik:

S → t O r
O → o O | o

Du findest sie in FLACI: Grammatik „tor“ in FLACI öffnen.

1. Bringe die Schritte der Ableitung von tooor in die richtige Reihenfolge.
2. Wie oft wird die Regel O → o O für ein Wort mit zehn o benutzt? Wie viele Ableitungsschritte sind insgesamt nötig?
3. Beschreibe die Sprache dieser Grammatik in eigenen Worten.

Zuerst gibt es nur die Befehle v und d. S steht für ein Programm, B für einen Befehl:

S → B S | ε
B → v | d

Du findest sie in FLACI: Grammatik 1 in FLACI öffnen.

1. Leite vdv ab. Schreibe jede Satzform auf. Prüfe mit der Satzformliste in FLACI.
2. Welches ist das kürzeste Programm, das sich ableiten lässt? Gibt es ein längstes?
3. Gib die Grammatik als Tupel G = (N, T, P, S) an.
4. Ein Experiment: Ändere in FLACI die erste Regel in S -> BS | EPSILON (ohne Leerzeichen) und leite vdv noch einmal ab. Was passiert? Erkläre es. Denke an das Alphabet Σ_chem aus dem Kapitel „Formale Sprachen“, in dem He ein einzelnes Symbol ist. Formuliere eine Merkregel für das Eintippen. Über den Link lädst du die Grammatik neu.

Jetzt soll Robo auch Blöcke [ ... ] verstehen. Dazu bekommt B eine dritte Alternative. In der Klammer steht wieder ein ganzes Programm:

S → B S | ε
B → v | d | [ S ]

Auch diese Grammatik findest du in FLACI: Grammatik 2 in FLACI öffnen.

1. Stelle v[dv]d mit der Maschine her. Schreibe die Satzformen auf und vergleiche sie mit der Satzformliste in FLACI.
2. Entscheide zuerst ohne FLACI, welche Programme ableitbar sind: [[v]], [v, [], v]d, [v][d]. Teste danach in FLACI.
3. In keinem ableitbaren Programm steht eine öffnende Klammer ohne die passende schließende. Erkläre, warum. Betrachte, durch welche Regel Klammern entstehen.
4. Die Grammatik besteht aus nur fünf Regeln: S → B S, S → ε, B → v, B → d und B → [ S ]. Trotzdem lassen sich unendlich viele Programme ableiten. Wie ist das möglich?
   Du kommst nicht weiter?

   Leite v[dv]d noch einmal ab. Welche Nichtterminalsymbole tauchen in den Satzformen immer wieder auf? Durch welche Regeln kommen sie zurück?

   Das hast du entdeckt – zum Nachlesen

   Eine Regel heißt rekursiv, wenn ihr Nichtterminalsymbol auf der rechten Seite wieder vorkommt (S → B S) oder sich über andere Regeln wieder erzeugt (B → [ S ], S → B S). Mit ihnen lassen sich beliebig lange oder tief verschachtelte Wörter erzeugen. In den Satzformen sieht man es daran, dass ein ersetztes Nichtterminalsymbol im nächsten Schritt wieder auftaucht.

Stehen in einer Satzform mehrere Nichtterminalsymbole, darfst du frei wählen, welches du zuerst ersetzt. Probiere es mit Grammatik 2 aus:

1. Stelle v[dv]d her. Ersetze dabei immer das Nichtterminalsymbol, das am weitesten links steht. Schreibe die Satzformen auf.
2. Stelle v[dv]d noch einmal her. Ersetze jetzt immer das Nichtterminalsymbol ganz rechts.
3. Vergleiche beide Herstellungen: Was ist gleich, was anders?
4. Öffne Grammatik 2 in FLACI. Leite v[dv]d ab und schalte zwischen L (links) und R (rechts) um. Vergleiche in beiden Einstellungen die Satzformliste. Was ändert sich, was bleibt gleich?

Robo soll leere Blöcke nicht mehr akzeptieren: [] soll ungültig sein. Das leere Programm bleibt gültig.

1. Ändere in Grammatik 2 nur die Regel für B.
2. Prüfe die Programme [], [v] und v[[d]].

Die Grammatiken haben die Terminalsymbole a und b, das Startsymbol ist S. Erkläre jeweils, welche Sprache L(G) die Grammatik G erzeugt. Gib das kürzeste Wort und drei möglichst unterschiedliche Beispielwörter an. Prüfe deine Vermutungen in FLACI. Aufgabe a) ist als Beispiel gelöst.

1. S → a S | b
   Erklärung: beliebig viele a, am Ende genau ein b.
   kürzestes Wort: b
   weitere Beispiele: ab  aaaab  aaaaaaaaaab
2. S → a S | b S | ε
3. S → a S a | b
4. S → A A
A → a A | b

Entwirf in FLACI eine Grammatik für alle Wörter aus einigen a, gefolgt von genau so vielen b. Mindestens ein a kommt vor. Teste alle Beispiele.

Passe deine Grammatik an:

1. Auch das leere Wort soll zur Sprache gehören.
2. Auf jedes a sollen genau zwei b folgen (abb, aabbbb, …). Das leere Wort gehört nicht dazu.

1. Entwirf eine Grammatik für alle korrekt geschachtelten Klammerausdrücke aus ( und ). Das leere Wort gehört dazu.

   ableitbar	nicht ableitbar
   (), (()), ()(), (()())	)(, ((), ()), (()))(

   Rückblick: Klammerausdrücke als Syntaxdiagramme

   Im Kapitel „Syntaxdiagramme“ hast du Klammerausdrücke mit zwei Diagrammen beschrieben, die aufeinander verweisen. Dort gehörte das leere Wort nicht dazu:

   Übersetze die Diagramme in Regeln und passe sie dann für das leere Wort an.

2. Ein Palindrom ist ein Wort, das vorwärts und rückwärts gleich gelesen wird. Entwirf eine Grammatik für alle Palindrome aus a und b. Das leere Wort ist auch ein Palindrom.

   ableitbar	nicht ableitbar
   a, b, aba, abba, baab	ab, aab, abab, bba

   Rückblick: Palindrome als Syntaxdiagramm

   Im Kapitel „Syntaxdiagramme“ hast du nichtleere Palindrome so beschrieben:

3. Vergleiche deine Grammatik aus a) mit der einer Mitschülerin oder eines Mitschülers. Sind die Regeln gleich? Erzeugen beide dieselbe Sprache? Teste beide mit den Beispielen.

Diese Grammatik beschreibt einfache Rechenausdrücke. z steht für eine Zahl:

E → E + E | E * E | ( E ) | z

Du findest sie in FLACI: Grammatik „Rechenausdrücke“ in FLACI öffnen.

1. Leite z+z*z in FLACI als Linksableitung ab (Einstellung L). Finde von Hand eine zweite, andere Linksableitung für dasselbe Wort. Tipp: Beginne mit der Regel E → E * E.
2. Klammerprobe: Schreibe eine Ableitung noch einmal auf. Immer wenn du eine Regel mit + oder * anwendest, setzt du eckige Klammern um das, was dabei entsteht. Eckig, damit sie nicht mit den runden Klammern der Grammatik verwechselt werden. So siehst du, was zusammengehört. Für die Ableitung, die mit E → E + E beginnt, sieht das so aus:

   E ⇒ [E + E] ⇒ [z + E] ⇒ [z + [E * E]] ⇒ [z + [z * E]] ⇒ [z + [z * z]]

   Führe die Klammerprobe für deine zweite Ableitung durch. Setze dann für die drei z die Zahlen 2, 3 und 4 ein und rechne beide geklammerten Ausdrücke aus.
3. Im Kapitel „Syntaxdiagramme“ hast du Rechenausdrücke mit diesen Diagrammen beschrieben (ohne Vorzeichen gezeigt): Zeigen die Diagramme, ob in z+z*z zuerst addiert oder zuerst multipliziert wird? Vergleiche mit deinen Klammerproben aus b).
4. Auch natürliche Sprache kann mehrdeutig sein: „Ich sehe den Mann mit dem Fernglas.“ Gib zwei Lesarten an. Warum ist so etwas bei Programmiersprachen ein Problem?

Entwirf in FLACI eine Grammatik für dieselben Rechenausdrücke wie in Aufgabe 9, die aber eindeutig ist und „Punkt vor Strich“ beachtet: Für z+z*z soll es nur eine Linksableitung geben, und ihre Klammerprobe soll [z + [z * z]] ergeben.

1. Teste deine Grammatik mit z+z*z, z*z+z, (z+z)*z und z+*z. Welche Wörter sind ableitbar?
2. Schreibe die Linksableitung von z+z*z mit Klammerprobe auf. Gibt es jetzt noch eine andere Linksableitung?
3. Beide Grammatiken erzeugen dieselben Wörter. Was unterscheidet sie, und warum ist das für die Bedeutung eines Rechenausdrucks wichtig?

Entwirf in FLACI eine Grammatik für alle Wörter aus einigen a, genauso vielen b und genauso vielen c, in dieser Reihenfolge. Mindestens ein a kommt vor.

1. Im Kapitel „Syntaxdiagramme“ hast du erfahren, dass sich diese Sprache nicht mit Syntaxdiagrammen beschreiben lässt. Gelingt es mit einer Grammatik? Versuche, eine zu finden. Bei Aufgabe 7 hat der Trick mit a S b funktioniert. Woran scheitert dein Versuch bei drei Buchstaben?
2. Formuliere eine Vermutung, woran das liegen könnte. Vergleiche mit der Begründung aus dem Kapitel „Syntaxdiagramme“.