Grammatiken und Ableitungen: Übungen – Informatik Leistungskurs

A1

Bestandteile einer Grammatik

AFB I

Gegeben ist die Grammatik G_X mit N = {S, R}, T = {x, y, +}, Startsymbol S und den Regeln S → xR | yR, R → +S | ε. Ordnen Sie jeden Bestandteil zu.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).

1Nichtterminal

2Terminal

3Produktionsregel

Nichtterminale (groß) werden ersetzt, Terminale (klein oder Zeichen wie +) bleiben im fertigen Wort stehen. Regeln erkennt man am Pfeil. Typischer Fehler: + für ein Nichtterminal halten, weil es kein Buchstabe ist — es gehört aber zum fertigen Wort.

Ansatz: Welche Symbole stehen im fertigen Wort, welche werden noch ersetzt?

Weiter: Schauen Sie in N und T nach — dort ist jedes Symbol aufgelistet.

A2

Stimmt das? — Ableiten

AFB I

Nennen Sie zu jeder Aussage, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.

Aussage 1 von 5

Entscheidend ist der Unterschied zwischen Satzform und Wort: Erst wenn kein Nichtterminal mehr übrig ist, ist ein Wort der Sprache erreicht.

Ansatz: Unterscheiden Sie Zwischenergebnis und Endergebnis.

Weiter: Der Oder-Strich fasst Alternativen zusammen.

A3

Beispiele zu G_X

AFB I

Betrachten Sie G_X aus A1. Geben Sie zu jedem Begriff ein passendes Beispiel an, indem Sie beide verbinden.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

x+S ist eine Satzform: Sie enthält noch das Nichtterminal S. x+y besteht nur aus Terminalen und ist ableitbar: S ⇒ xR ⇒ x+S ⇒ x+yR ⇒ x+y.

Ansatz: Beginnen Sie mit dem Startsymbol und der ε-Regel.

Weiter: Eine Satzform enthält noch mindestens ein Nichtterminal.

A4

Linksableitung von y+x

AFB II

Wenden Sie die Regeln von G_X (A1) an und leiten Sie y+x Schritt für Schritt ab. Tragen Sie jeweils die Satzform ein.

Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.

Satzform nach dem 1. Schritt
nach dem 2. Schritt
nach dem 3. Schritt
nach dem 4. Schritt
Anzahl der Ableitungsschritte

S ⇒ yR ⇒ y+S ⇒ y+xR ⇒ y+x. Im letzten Schritt verschwindet R durch R → ε. Typischer Fehler: nach y+x aufhören, ohne R zu beseitigen — y+xR ist noch eine Satzform.

Ansatz: Welche Regel für S liefert ein y am Anfang?

Weiter: Am Ende bleibt ein R übrig — welche Regel lässt es verschwinden?

A5

Ableitbar oder nicht?

AFB II

Gegeben ist G_A mit N = {S, B}, T = {a, b}, Startsymbol S und S → aS | bB, B → bB | ε. Ermitteln Sie für jedes Wort, ob es zu L(G_A) gehört, und die Anzahl der Ableitungsschritte (– wenn nicht ableitbar).

Tragen Sie „ja“/„nein“ und die Schrittzahl ein (– für „nicht ableitbar“) und prüfen Sie dann.

Wort	a	b	ba	aabbb
in L(G_A)?
Schritte

L(G_A) enthält alle Wörter aus beliebig vielen a und danach mindestens einem b. Für aabbb: S ⇒ aS ⇒ aaS ⇒ aabB ⇒ aabbB ⇒ aabbbB ⇒ aabbb — 6 Schritte, denn B → ε ist auch ein Schritt. a fehlt das b, bei ba kann nach dem b kein a mehr kommen.

Ansatz: Welche Regel beendet eine Ableitung? Was muss vorher passiert sein?

Weiter: Zählen Sie jede Regelanwendung als einen Schritt — auch B → ε.

A6

Ableitung ordnen

AFB II

Die Grammatik G_P hat die Regeln S → aSa | bSb | c. Ordnen Sie die Satzformen der Ableitung von abacaba in die richtige Reihenfolge ein.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1S

2aSa

3abSba

4abaSaba

5abacaba

Jede Regel S → aSa bzw. S → bSb setzt ein Zeichenpaar außen um das S — die Wörter wachsen von außen nach innen. Zum Schluss ersetzt S → c das S in der Mitte. Typischer Fehler: die Paare von links nach rechts zu lesen statt von außen nach innen.

Ansatz: Jede Satzform ist um zwei Zeichen länger als die vorige.

Weiter: Das äußerste Paar entsteht im ersten Schritt.

A7

Grammatik trifft Keller

AFB II Mix

Vergleichen Sie G_P aus A6 mit dem Kellerautomaten für \(\{w\,c\,w^R\}\) aus 9.2.4 und markieren Sie alle zutreffenden Aussagen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.

Grammatik und Kellerautomat beschreiben dieselbe Sprache von zwei Seiten: Die Grammatik erzeugt, der Automat prüft. Die Paare außen um S entsprechen dem Ablegen und Vergleichen im Keller. Das kürzeste Wort ist c; abcab ist nicht symmetrisch. Einen DEA gibt es nach 9.2.2 nicht.

Ansatz: Leiten Sie ein paar kurze Wörter ab: c, aca, bcb, abcba.

Weiter: Wie hängen „Paar außen hinzufügen“ und „ablegen, dann vergleichen“ zusammen?

A8

Fehlersuche: x+y+x

AFB III

Mila leitet x+y+x in G_X (A1) ab und kommentiert den Baum. Überprüfen Sie ihre Lösung — drei Zeilen sind fehlerhaft.

In dieser Lösung stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.

Zeile 5 stimmt: Die Wurzel ist immer das Startsymbol. Die Fehler: eine erfundene Regel, ein falscher Schluss aus einer ε-Regel und eine Verwechslung von inneren Knoten und Blättern.

Ansatz: Prüfen Sie jeden Schritt: Steht die benutzte Regel wirklich in G_X?

Weiter: Kann aus S überhaupt ein Wort ohne x oder y entstehen?

A9

Eine Grammatik für aⁿb²ⁿ

AFB III

Zu \(L=\{a^nb^{2n}\mid n\ge 0\}\) wurde in 9.2.4 ein Kellerautomat gebaut. Jetzt soll eine Grammatik mit einem einzigen Nichtterminal S die Sprache erzeugen. Entwickeln Sie sie, indem Sie die Menüs ausfüllen.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

Regeln für S:

Ableitung von aabbbb:

Anzahl der Ableitungsschritte für \(a^nb^{2n}\):

Welcher Automat erkennt L?

Jede Anwendung von S → aSbb setzt ein a links und zwei b rechts um das S; S → ε beendet die Ableitung. Das ergibt n Schritte für die Paare und einen für ε. S → aSbb | abb vergisst n = 0 (ε ∈ L). Wie beim Kellerautomaten in 9.2.4 ist die Sprache nicht regulär.

Ansatz: Welche rechte Seite erzeugt pro Schritt ein a und zwei b — und zwar an den richtigen Stellen?

Weiter: Gehört ε zu L? Dann braucht S eine ε-Regel.

A10

Unendlich viele Wörter?

AFB III Trick

Paul betrachtet G_T mit N = {S, A}, T = {a, b} und den Regeln S → aS | A, A → Ab. Er sagt: „Wegen der Schleife S → aS erzeugt G_T unendlich viele Wörter.“ Beurteilen Sie die Aussage, indem Sie angeben, wie viele Wörter L(G_T) tatsächlich enthält.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.

Die Falle: Es gibt zwar unendlich viele Satzformen (S, aS, aaS, …, aaAbb …), aber keine davon lässt sich zu einem Wort ohne Nichtterminale ableiten — A wird nie los, weil A → Ab immer wieder A erzeugt. L(G_T) = ∅. Pauls Aussage ist falsch: Nur ableitbare Terminalwörter zählen.

Ansatz: Versuchen Sie, ein einziges Wort vollständig abzuleiten.

Weiter: Gibt es eine Regel, die A ohne neues Nichtterminal ersetzt?

Übungen: Grammatiken

Übungsaufgaben