Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

Fachkonzept - Grammatik

Ein Beispiel

Als Beispiel betrachten wir die vereinfachten E-Mail-Adressen aus einem der letzten Abschnitte.

Grammatik - in Langform Grammatik - in Kurzform
emailadresse -> user @ domain
user -> name
domain -> subdomains topleveldomain
subdomains -> name .
subdomains -> name . subdomains
topleveldomain -> name
name -> buchstabe
name -> buchstabe name
buchstabe -> b
E -> U@D
U -> N
D -> ST
S -> N.
S -> N.S
T -> N
N -> B
N -> BN
B -> b

Die Grammatik legt genau fest, wie eine (vereinfachte) E-Mail-Adresse gebildet werden kann. Dabei wird das Bildungsgesetz mit Hilfe von Regeln beschrieben, die als Ersetzungsregeln benutzt werden. Im Folgenden soll dieser Ansatz, eine Sprache mit Ersetzungsregeln festzulegen, genauer beschrieben werden.

Bestandteile einer Grammatik

Wir präzisieren zunächst die Bestandteile einer Grammatik.

Eine Grammatik besteht aus den folgenden Komponenten:
  • einer endlichen nichtleeren Menge T von Terminalsymbolen (Alphabet der betreffenden Sprache)
  • einer endlichen nichtleeren Menge N von Nichtterminalsymbolen (Hilfsymbole)
  • einer endlichen Menge P von Produktionen (Ersetzungsregeln)
  • einem Startsymbol S ∈ N (zum Starten einer Ableitung)
Hierfür schreibt man auch kurz: G = (T, N, P, S).

Im Zentrum stehen dabei die sogenannten Produktionen.

Eine Produktion hat die Gestalt u -> v. Die linke Seite u und die rechte Seite v sind dabei Wörter über dem Alphabet V = T ∪ N sämtlicher Symbole. Die linke Seite u muss mindestens ein Nichtterminalsymbol aus N enthalten.

Beispiel 1:

E -> U@D
U -> N
D -> ST
S -> N.
S -> N.S
T -> N
N -> B
N -> BN
B -> b

Hier gilt:

Beachte, dass das Startsymbol oft durch die linke Seite der ersten aufgelisteten Regel implizit festgelegt wird.

Beispiel 2:

E -> bU@D
U -> bU
U -> λ 
D -> bS
S -> bS
S -> .bS
.bS -> .bT
T -> bT
T -> λ 

Hier gilt:

Dieses Beispiel zeigt, dass eine Produktion das leere Wort λ als rechte Seite einer Produktion haben kann. Es zeigt auch, dass auf der linken Seite einer Produktion komplexere Wörter stehen können.

Worterzeugung mit Ableitungen

Produktionen einer Grammatik dienen zur Worterzeugung.

Eine Ableitung beginnt immer mit dem Startsymbol. Sie endet, wenn alle Nichtterminalsymbole ersetzt sind. Ein Ableitungsschritt besteht darin, ein Teilwort innerhalb eines Worts mit Hilfe einer passenden Produktion zu ersetzen. Produktionen sind demnach Ersetzungsregeln.

Beispiel 1 (s.o.):

E -> U@D
U -> N
D -> ST
S -> N.
S -> N.S
T -> N
N -> B
N -> BN
B -> b

Ableitung des Worts bb@b.bbb.bb mit den Produktionen:

E ->             # mit der Regel E -> bU@D
bU@D ->          # mit der Regel U -> N
bN@D ->          # mit der Regel N -> B
bB@D ->          # mit der Regel B -> b
bb@D ->          # mit der Regel D -> ST
bb@ST ->         # mit der Regel S -> N.S
bb@N.ST ->       # mit der Regel S -> N.
bb@N.N.T ->      # mit der Regel N -> B
bb@B.N.T ->      # mit der Regel B -> b
bb@b.N.T ->      # mit der Regel N -> BN
bb@b.BN.T ->     # mit der Regel N -> BN
bb@b.BBN.T ->    # mit der Regel N -> B
bb@b.BBB.T ->    # mit der Regel B -> b
bb@b.bBB.T ->    # mit der Regel B -> b
bb@b.bbB.T ->    # mit der Regel B -> b
bb@b.bbb.T ->    # mit der Regel T -> N
bb@b.bbb.N ->    # mit der Regel N -> BN
bb@b.bbb.BN ->   # mit der Regel B -> b
bb@b.bbb.bN ->   # mit der Regel N -> B
bb@b.bbb.bB ->   # mit der Regel B -> b
bb@b.bbb.bb

Beispiel 2 (s.o.):

E -> bU@D
U -> bU
U -> λ 
D -> bS
S -> bS
S -> .bS
.bS -> .bT
T -> bT
T -> λ 

Ableitung des Worts bb@b.bbb.bb mit den Produktionen:

E ->             # mit der Regel E -> U@D
U@D ->           # mit der Regel U -> bU
bU@D ->          # mit der Regel U -> bU
bbU@D ->         # mit der Regel U -> λ
bb@D ->          # mit der Regel D -> bS
bb@bS ->         # mit der Regel S -> .bS
bb@b.bS ->       # mit der Regel S -> bS
bb@b.bbS ->      # mit der Regel S -> bS
bb@b.bbbS ->     # mit der Regel S -> .bS
bb@b.bbb.bS ->   # mit der Regel .bS -> .bT
bb@b.bbb.bT ->   # mit der Regel T -> bT
bb@b.bbb.bbT ->  # mit der Regel T -> λ
bb@b.bbb.bb

Beachte, dass es auch verschiedene Ableitungen zu einem Wort geben kann.

Sprachfestlegung mit einer Grammatik

Eine Grammatik legt eine Sprache fest.

Die von einer Grammatik G=(T, N, P, S) erzeugte Sprache L(G) ist die Menge aller Wörter über dem Alphabet T, die vom Startsymbol S mit Hilfe der Produktionen aus P abgeleitet werden können. von G erzeugte Sprache.

Beachte, dass verschiedene Grammatiken dieselbe Sprache erzeugen können. So erzeugen die Grammatiken aus Beispiel 1 (s.o.) und Beispiel 2 (s.o.) dieselbe Sprache (der stark vereinfachten E-Mail-Adressen).

X

Fehler melden

X

Suche