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:

  (1) <Fernstraße> -> <Autobahn>
  (2) <Fernstraße> -> <Bundesstraße>
  (3) <Autobahn> -> 'A'<ZahlMaxDreistellig>
  (4) <Bundestraße> -> 'B'<ZahlMaxDreistellig>
  (7) <ZahlMaxDreistellig> -> <Ziffer>
  (6) <ZahlMaxDreistellig> -> <Ziffer><Ziffer>
  (8) <ZahlMaxDreistellig> -> <Ziffer><Ziffer><Ziffer>
  (9) <Ziffer> -> '1'
  (10) <Ziffer> -> '2'
  (11) <Ziffer> -> '3'
  (12) <Ziffer> -> '4'
  (13) <Ziffer> -> '5'
  (14) <Ziffer> -> '6'
  (15) <Ziffer> -> '7'
  (16) <Ziffer> -> '8'
  (17) <Ziffer> -> '9'
  (18) <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'

Aufgabe 1

Geben Sie die Ableitungen der Wörter "A34" und "B903" an.

Lösung

$$<Fernstraße>\xrightarrow[]{(1)}<Autobahn>\xrightarrow[]{(3)}\mathrm{A}<ZahlMaxDreistellig>\xrightarrow[]{(6)}\mathrm{A}<Ziffer><Ziffer>$$ $$\xrightarrow[]{(11)}\mathrm{A3}<Ziffer>\xrightarrow[]{(12)}\mathrm{A34}<Ziffer>$$

$$<Fernstraße>\xrightarrow[]{(2)}<Bundesstraße>\xrightarrow[]{(4)}\mathrm{B}<ZahlMaxDreistellig>\xrightarrow[]{(8)}\mathrm{B}<Ziffer><Ziffer><Ziffer>$$ $$\xrightarrow[]{(17)}\mathrm{B9}<Ziffer><Ziffer>\xrightarrow[]{(18)}\mathrm{B90}<Ziffer>\xrightarrow[]{(11)}\mathrm{B903}$$

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.

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:

  (1) <Zahl> -> <Ziffer> | <Ziffer><Zahl>
  (2) <Ziffer> -> "0" | "1" | ... | "9"

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

Aufgabe 4

Verändern sie obige Grammatik G so, dass

keine Vornullen erlaubt sind und
die Sprache genau die Dezimaldarstellungen aller ganzen Zahlen umfasst.

Aufgabe 4

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 + a - b + b$ usw.