Erzeugung formaler Sprachen

Um festzulegen, welche Wörter zu einer Sprache gehören, formuliert man meist eine Menge von Regeln (Syntax), nach denen alle Wörter der Sprache aus ihrem Alphabet gebildet werden können (Produktionsregeln).
Die Bildung eines Wortes mithilfe der Produktionsregeln nennt man seine Ableitung.

Beispiel: Bezeichnung von Fernstraßen in Deutschland

Die Bezeichnungen aller Bundsstraßen und Autobahnen in Deutschland ist eine Sprache über dem Alphabet A = {A, B, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, die durch folgende Produktionsregeln ( = Syntax) definiert wird:

  R1: Fernstraße = Autobahn
  R2: Fernstraße = Bundesstraße
  R3: Autobahn = "A"ZahlMaxDreistellig
  R4: Bundestraße = "B"ZahlMaxDreistellig
  R7: ZahlMaxDreistellig = Ziffer
  R6: ZahlMaxDreistellig = ZifferZiffer
  R8: ZahlMaxDreistellig = ZifferZifferZiffer
  R9: Ziffer = "1"
  R10: Ziffer = "2"
  R11: Ziffer = "3"
  R12: Ziffer = "4"
  R13: Ziffer = "5"
  R14: Ziffer = "6"
  R15: Ziffer = "7"
  R16: Ziffer = "8"
  R17: Ziffer = "9"
  R18: Ziffer = "0"

Begriffe:
Kommt in den Produktionsregeln ein Element des Alphabets vor, so bezeichnet man es als Terminal, weil es sich im Verlauf der Ableitung eines Wortes nicht mehr ändert. Die Variablen Fernstraße, Autobahn, … bezeichnet man als Nichtterminale, weil sie im Lauf der Ableitung noch ersetzt werden müssen.

Kurzschreibweise:
Falls mehrere Produktionsregeln auf der linken Seite das selbe Nichtterminalsymbol haben, kann man sie mit Hilfe des Operators | ("oder") zu einer zusammenfassen. Die Regeln 9 - 18 oben kann man bspw. zusammenfassen zu

Ziffer = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"

Backus-Naur-Form
Die oben beschriebene Form, mit der wir Produktionsregeln angeben können, bezeichnet man als Backus-Naur-Form (BNF). Wir werden etwas später noch die erweiterte Backus-Naur-Form (EBNF) kennenlernen, die exakt gleich mächtig ist, jedoch in vielen Fällen eine kompaktere, griffigere Darstellung der Produktionen ermöglicht.

Aufgabe 1

Geben Sie die Ableitungen der Wörter "A34" und "B903" an und zeichnen Sie zur ersten der beiden Ableitungen einen Ableitungsbaum.

Lösung

$$Fernstraße\xrightarrow[]{(R1)}Autobahn\xrightarrow[]{(R3)}\mathrm{"A"}ZahlMaxDreistellig\xrightarrow[]{(R6)}\mathrm{"A"}Ziffer\ Ziffer$$ $$\xrightarrow[]{(R11)}\mathrm{"A3"}Ziffer\xrightarrow[]{(R12)}\mathrm{"A34"}Ziffer$$

$$Fernstraße\xrightarrow[]{(R2)}Bundesstraße\xrightarrow[]{(R4)}\mathrm{"B"}ZahlMaxDreistellig\xrightarrow[]{(R8)}\mathrm{"B"}Ziffer\ Ziffer\ Ziffer$$ $$\xrightarrow[]{(R17)}\mathrm{"B9"}Ziffer\ Ziffer\xrightarrow[]{(R18)}\mathrm{"B90"}Ziffer\xrightarrow[]{(R11)}\mathrm{"B903"}$$

Zur ersten der beiden Ableitungen hier der Ableitungsbaum:

Aufgabe 2

Ist die Ableitung eines Wortes immer eindeutig? Begründen Sie Ihre Antwort beispielhaft mit den obigen Produktionsregeln!

Definition:

Eine formale Grammatik $$G = (V, A, P, S)$$ besteht aus

der Menge der Nichtterminale $V$
dem Alphabet $A$
einer Menge von Produktionsregeln $P$ und
einem Startsymbol $S\in V$

Dabei müssen $A$ und $V$ disjunkt sein, d.h. $A \bigcap V = \{\}$.
$G$ definiert eine formale Sprache, die aus allen Wörtern aus $A^*$ besteht, die aus dem Startsymbol $S$ durch Anwendung endlich vieler Produktionsregeln aus $P$ abgeleitet werden können.

Aufgabe 3

a) Geben Sie eine Grammatik an, die Sprache beschreibt, in der deutsche Autokennzeichen notiert werden.

Die Sprache soll alle Autokennzeichen der Formen "ND WW 16" und "IN XE 312E" beschreiben (Ortskürzel mit bis zu drei Buchstaben, Zwischenbereich mit bis zu zwei Buchstaben, ein- bis dreistellige Zahl, optional "E" am Ende).
Auch nichtexistente Ortskürzel dürfen vorkommen.

b) Geben Sie zur Grammatik aus a) die Ableitung des Kennzeichens "SOB AX 12E" an.

Lösung

Rekursive Produktionsregeln

Gegeben ist die Grammatik $G = (V, A, P, S)$ mit dem Alphabet $A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, den Nichtterminalen $V=\{Zahl,\ Ziffer\}$, dem Startsymbol $S = Zahl$ und folgenden Produktionsregeln:

  R1: Zahl = Ziffer | Ziffer Zahl
  R2: Ziffer = "0" | "1" | ... | "9"

Beschreiben Sie die Semantik der erzeugten Sprache! Inwiefern sind diese Produktionsregeln rekursiv?

Aufgabe 4

Erweitern sie obige Grammatik G so, dass die Sprache genau die Dezimaldarstellungen aller ganzen Zahlen umfasst, wobei keine Vornullen erlaubt sein sollen.

Aufgabe 5

Geben Sie eine Grammatik einer Sprache an, die alle ungeklammerten Terme enthält, die

nur die Rechenzeichen + und - sowie
als Operanden nur die Variablen a, b und c besitzen.

Gemeint sind also Terme der Form $a$, $b$, $c$, $a + b$, $a - b$, $a + b - c$, $a + a - b + b$ usw.

Aufgabe 6

Die Sprache aller symmetrischen Wörter über den Alphabet $A = \{a, b\}$ enthält das leere Wort $\varepsilon$, die Wörter $a$, $b$, $aa$, $bb$, $aba$, usw.

Geben Sie eine Grammatik an, die diese Sprache erzeugt.