MINT lernen

Abituraufgaben: Grammatiken

Artikelnummern im Onlineshop und Zugangscodes fürs WLAN — Regeln, die Wörter Zeichen für Zeichen bauen.

Dein Fortschritt:
0 / 0 Aufgaben
1

Artikelnummern im Onlineshop

13 BEAFB I–II

Ein Onlineshop vergibt Artikelnummern aus zwei Buchstaben, einem Bindestrich und mindestens einer Ziffer, z. B. HT-4 oder KA-0815. Zur Prüfung wird jeder Buchstabe durch b und jede Ziffer durch z ersetzt; der Bindestrich bleibt. Die Nummern werden durch die folgende Grammatik G beschrieben:

N = {S, A, B, C, D}
T = {b, z, -}
Startsymbol: S
Produktionsregeln:
S → bA
A → bB
B → -C
C → zD
D → zD | ε
  1. Wenden Sie G an: Geben Sie eine Ableitung für bb-zz an und begründen Sie, warum b-z nicht abgeleitet werden kann. (3 BE)
  2. Beschreiben Sie die Bedeutung der Nichtterminale B und D sowie die von G erzeugte Sprache in Worten. (3 BE)
  3. Begründen Sie, dass G eine reguläre Grammatik ist. (2 BE)
  4. Artikel in Varianten erhalten zusätzlich einen Bindestrich und genau einen Buchstaben, z. B. KA-0815-R; Nummern ohne Zusatz bleiben gültig. Erweitern Sie G entsprechend und geben Sie eine Ableitung für bb-z-b an. (5 BE)

Hinweise

Hinweis zu Aufgabe a)
Ein Ableitungsschritt ersetzt das Nichtterminal am Ende der Satzform. Welche Regel hat A?
Hinweis zu Aufgabe b)
Fragen Sie für jedes Nichtterminal: Was ist bis hierher schon erzeugt, was fehlt noch?
Hinweis zu Aufgabe c)
Vergleichen Sie jede Regel mit den erlaubten Formen X → aY, X → a und X → ε.
Hinweis zu Aufgabe d)
Nach der letzten Ziffer (in D) darf jetzt auch ein Bindestrich kommen. Danach muss genau ein Buchstabe folgen — und dann ist Schluss.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

S ⇒ bA ⇒ bbB ⇒ bb-C ⇒ bb-zD ⇒ bb-zzD ⇒ bb-zz

b-z: Nach S ⇒ bA ist A das einzige Nichtterminal. A hat nur die Regel A → bB; ein Bindestrich direkt nach dem ersten b ist nicht möglich.

Erwartungshorizont zu Aufgabe b)

B: zwei Buchstaben erzeugt, der Bindestrich fehlt noch. D: Bindestrich und mindestens eine Ziffer erzeugt; es dürfen weitere Ziffern folgen oder das Wort endet.

L(G) = {bb-zⁿ | n ≥ 1}: zwei Buchstaben, ein Bindestrich, mindestens eine Ziffer — genau die gültigen Artikelnummern.

Erwartungshorizont zu Aufgabe c)

Jede Regel hat die Form X → aY (S → bA, A → bB, B → -C, C → zD, D → zD) oder X → ε (D → ε): rechts steht genau ein Terminal, gefolgt von höchstens einem Nichtterminal. Damit ist G regulär.

Erwartungshorizont zu Aufgabe d)

N = {S, A, B, C, D, E}; geänderte bzw. neue Regeln: D → zD | -E | ε und E → b.

S ⇒ bA ⇒ bbB ⇒ bb-C ⇒ bb-zD ⇒ bb-z-E ⇒ bb-z-b

E → b ohne Nichtterminal sorgt für „genau ein Buchstabe, dann Ende“. Würde der Weg nach dem zweiten Bindestrich zurück zu C oder D führen, wären auch bb-z-z oder mehrere Zusätze erlaubt.

2

Zugangscodes fürs WLAN

17 BEAFB II–III

Gäste im Schul-WLAN erhalten Zugangscodes aus Buchstaben (b) und Ziffern (z). Ein Code ist gültig, wenn er mindestens eine Ziffer enthält und mit einem Buchstaben endet, z. B. zb, bbzzb oder zbzb. Ungültig sind etwa bbb, bz und das leere Wort.

  1. Entwerfen Sie eine reguläre Grammatik G über T = {b, z}, die genau die gültigen Codes erzeugt. Geben Sie die Bedeutung jedes Nichtterminals an. (6 BE)
  2. Stellen Sie mit Ihrer Grammatik Ableitungen für zb und bzzb dar und begründen Sie, dass bz nicht ableitbar ist. (4 BE)
  3. Zusätzlich soll jeder Code 8 bis 12 Zeichen lang sein. Schätzen Sie ab, wie viele Nichtterminale eine reguläre Grammatik dafür höchstens braucht, und begründen Sie, dass die Sprache regulär bleibt. (3 BE)
  4. Die IT-Abteilung schlägt vor, nur noch Codes mit gleich vielen Buchstaben wie Ziffern zuzulassen. Erörtern Sie, ob sich diese Codes ohne und mit der Längengrenze aus c) durch eine reguläre Grammatik beschreiben lassen. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Was muss man über das bisher erzeugte Anfangsstück wissen? Ob schon eine Ziffer vorkam — und womit es zuletzt endete. Das ergibt drei Situationen.
Hinweis zu Aufgabe b)
Schreiben Sie die Satzformen Schritt für Schritt auf. Bei bz: Welches Nichtterminal steht nach dem z am Ende, und darf es verschwinden?
Hinweis zu Aufgabe c)
Neben der Information aus a) muss sich die Grammatik die bisherige Länge merken. Wie viele Kombinationen gibt es höchstens?
Hinweis zu Aufgabe d)
Denken Sie an {aⁿbⁿ | n ≥ 0} aus 9.2.2. Was ändert eine feste Obergrenze der Länge?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

N = {S, A, B}, T = {b, z}, Startsymbol: S

S → bS | zA
A → zA | bB
B → bB | zA | ε

S: noch keine Ziffer erzeugt. A: mindestens eine Ziffer, zuletzt eine Ziffer. B: mindestens eine Ziffer, zuletzt ein Buchstabe — nur hier ist der Code gültig, deshalb hat nur B eine ε-Regel.

Erwartungshorizont zu Aufgabe b)

zb: S ⇒ zA ⇒ zbB ⇒ zb

bzzb: S ⇒ bS ⇒ bzA ⇒ bzzA ⇒ bzzbB ⇒ bzzb

bz: Jede Ableitung beginnt mit S ⇒ bS ⇒ bzA. A hat keine ε-Regel, also muss noch mindestens ein Zeichen folgen; bz selbst entsteht nie.

Erwartungshorizont zu Aufgabe c)

Jedes Nichtterminal muss jetzt zwei Informationen tragen: die Situation aus a) (S, A oder B) und die bisherige Länge 0 bis 12. Das sind höchstens 3 · 13 = 39 Nichtterminale (einige davon sind unerreichbar, etwa B mit Länge 0). ε-Regeln gibt es nur bei B mit Länge 8 bis 12, bei Länge 12 keine Regel mit weiterem Zeichen.

Es bleiben endlich viele Nichtterminale mit Regeln der festen Form — die Sprache ist regulär.

Erwartungshorizont zu Aufgabe d)

Ohne Längengrenze: Die Grammatik müsste sich die Differenz „Ziffern minus Buchstaben“ merken, und die ist unbeschränkt. Angenommen, eine reguläre Grammatik mit k Nichtterminalen erzeugt die Codes. In der Ableitung des gültigen Codes zⁱbⁱ steht nach zⁱ ein Nichtterminal Xᵢ (i = 1, …, k + 1). Nach dem Schubfachprinzip gilt Xᵢ = Xⱼ für ein i < j. Weil aus Xᵢ der Rest bⁱ ableitbar ist, entsteht auch zʲbⁱ — ein ungültiger Code. Widerspruch. Die Sprache ist nicht regulär, genau wie {aⁿbⁿ | n ≥ 0}.

Mit Längengrenze: Es gibt nur endlich viele Codes der Länge 8 bis 12. Die Differenz liegt zwischen −12 und 12 und lässt sich zusammen mit der Länge in endlich vielen Nichtterminalen speichern — regulär, aber mit vielen Regeln.

Fazit: Der Vorschlag ist nur wegen der Längengrenze mit einer regulären Grammatik umsetzbar.