MINT lernen

Abituraufgaben: Grammatiken

Programme für einen Lernroboter und E-Mail-Adressen — zwei Formate, die eine Grammatik exakt festlegt.

Dein Fortschritt:
0 / 0 Aufgaben
1

Programme für einen Lernroboter

13 BEAFB I–II

Ein Lernroboter versteht kurze Programme aus den Befehlen v (vorwärts), l (links drehen), r (rechts drehen) und der Wiederholung w( … ), die ihren Inhalt zweimal ausführt. Die erlaubten Programme beschreibt die Grammatik GR:

N =
{S, B}
T =
{v, l, r, w, (, )}
Startsymbol:
S
Produktionsregeln:
S → BS | B
B → v | l | r | w(S)
  1. Beschreiben Sie die Bedeutung der Nichtterminale S und B im Kontext des Roboters. (2 BE)
  2. Stellen Sie eine Linksableitung des Programms vw(lv) dar. Geben Sie bei jedem Schritt die verwendete Regel an. (4 BE)
  3. Zeichnen Sie den Ableitungsbaum zu vw(lv). (4 BE)
  4. Begründen Sie, dass w() und vv) nicht zu L(GR) gehören. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Was lässt sich aus B ableiten, was aus S?
Hinweis zu Aufgabe b)
Ersetzen Sie immer das am weitesten links stehende Nichtterminal. Das Programm besteht aus zwei Befehlen, v und w(lv).
Hinweis zu Aufgabe c)
Jeder Ableitungsschritt erzeugt Kinder unter dem ersetzten Nichtterminal — in der Reihenfolge der rechten Seite.
Hinweis zu Aufgabe d)
Kann S zu ε werden? Wie entstehen Klammern?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

B steht für einen einzelnen Befehl (v, l, r oder eine Wiederholung). S steht für ein Programm: eine nichtleere Folge von Befehlen — S → BS hängt einen Befehl vorn an, S → B beendet die Folge.

Erwartungshorizont zu Aufgabe b)

S ⇒ BS (S → BS) ⇒ vS (B → v) ⇒ vB (S → B) ⇒ vw(S) (B → w(S)) ⇒ vw(BS) (S → BS) ⇒ vw(lS) (B → l) ⇒ vw(lB) (S → B) ⇒ vw(lv) (B → v)

Erwartungshorizont zu Aufgabe c)
Lösung: Ableitungsbaum zu vw(lv)
SBvSBw(SBlSBv)

Innere Knoten sind S und B, die Blätter von links nach rechts ergeben vw(lv).

Erwartungshorizont zu Aufgabe d)

w(): Klammern entstehen nur mit B → w(S). Zwischen ihnen steht S, und S hat keine ε-Regel — jedes S erzeugt mindestens einen Befehl. Leere Klammern sind nicht ableitbar.

vv): Jede Regel erzeugt ( und ) gemeinsam, eine einzelne schließende Klammer kann nicht entstehen.

2

E-Mail-Adressen

17 BEAFB II–III

Ein Anmeldeformular soll E-Mail-Adressen prüfen. Vereinfacht steht b für einen beliebigen Buchstaben. Die Entwicklerin hat folgende Grammatik GM aufgestellt:

N =
{S, W, D}
T =
{b, @, .}
Startsymbol:
S
Produktionsregeln:
S → W@D
W → bW | b
D → W.W | W.D
  1. Überprüfen Sie, ob bb@b.bb, b@bb und @b.b zu L(GM) gehören. (3 BE)
  2. Weisen Sie durch eine Linksableitung nach, dass b@b.b.b zu L(GM) gehört. (4 BE)
  3. Adressen wie max.muster@… sollen erlaubt werden: Vor dem @ dürfen Punkte stehen, aber nicht am Anfang, nicht am Ende und nicht zwei hintereinander. Erweitern Sie GM entsprechend. (5 BE)
  4. Ein Mitschüler meint: „Eine Grammatik ist hier überflüssig — ein paar if-Abfragen im Programm reichen.“ Erörtern Sie diese Aussage. (5 BE)

Hinweise

Hinweis zu Aufgabe a)
W erzeugt mindestens ein b. Was verlangt D?
Hinweis zu Aufgabe b)
Die Domain b.b.b hat zwei Punkte — welche D-Regel kommt zuerst?
Hinweis zu Aufgabe c)
Führen Sie ein neues Nichtterminal für den Teil vor dem @ ein, das wie D Wörter mit Punkten verbindet — aber auch ohne Punkt enden darf.
Hinweis zu Aufgabe d)
Denken Sie an Eindeutigkeit, Dokumentation, Änderungen und daran, wie echte Standards Formate festlegen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
  • bb@b.bb: S ⇒ W@D, W ⇒* bb, D ⇒ W.W ⇒* b.bb — gehört dazu.
  • b@bb: D erzeugt immer mindestens einen Punkt — gehört nicht dazu.
  • @b.b: W vor dem @ erzeugt mindestens ein b — gehört nicht dazu.
Erwartungshorizont zu Aufgabe b)

S ⇒ W@D (S → W@D) ⇒ b@D (W → b) ⇒ b@W.D (D → W.D) ⇒ b@b.D (W → b) ⇒ b@b.W.W (D → W.W) ⇒ b@b.b.W (W → b) ⇒ b@b.b.b (W → b)

Erwartungshorizont zu Aufgabe c)

N = {S, L, W, D}, neue bzw. geänderte Regeln:

S → L@D
L → W | W.L

L erzeugt Wörter aus b-Blöcken, zwischen denen je genau ein Punkt steht. Weil jeder Block aus W mindestens ein b enthält, stehen Punkte nie am Anfang, nie am Ende und nie doppelt. Beispiel: S ⇒ L@D ⇒ W.L@D ⇒ … ⇒ b.bb@b.b.

Erwartungshorizont zu Aufgabe d)

Pro: Für ein so einfaches Format lassen sich die Bedingungen auch direkt programmieren; das kann schneller umgesetzt sein.

Contra: Die Grammatik ist eine eindeutige, kurze Beschreibung des Formats. Alle Beteiligten (Formular, Server, Mailprogramme) können sich darauf beziehen; Änderungen wie in c) betreffen nur einzelne Regeln. Aus Grammatiken lassen sich Prüfprogramme systematisch ableiten, während verstreute if-Abfragen leicht Sonderfälle übersehen (z. B. zwei Punkte hintereinander). Echte Standards wie die E-Mail-Norm legen Formate deshalb mit Grammatiken fest.

Fazit: Das Programm braucht am Ende Code — die Grammatik ist aber die verlässliche Grundlage dafür. Die Aussage greift zu kurz.