Theoretische Informatik

Grammatik

 aufwärts

Eine endliche Sprache lässt sich einfach durch Aufzählung aller ihrer Wörter angeben. Um eine unendliche Sprache angeben zu können, benötigt man eine endliche Beschreibung der Sprache. Eine solche existiert nur, wenn alle Wörter der Sprache einem bestimmten Bildungs­gesetz folgen (z.B. "alle Wörter, die mit a anfangen, mindestens fünf b's und genauso viele c's enthalten und mit a oder c aufhören"). Es gibt Sprachen, die keine endliche Beschreibung haben, denn es gibt über­abzählbar viele Sprachen, aber nur abzählbar viele endliche Beschreibungen.

In der Theorie der formalen Sprachen werden Grammatiken zur Beschreibung von Sprachen verwendet. Mithilfe einer Grammatik lassen sich die Wörter einer Sprache L erzeugen: Ein Wort gehört zu L, wenn es sich durch eine Folge von bestimmten zulässigen Ersetzungen aus einem sogenannten Startsymbol erzeugen lässt.

Grammatik

Definition:  Eine Grammatik ist ein 4-Tupel

G = (V, T, P, S).

Hierbei ist

V das Alphabet der Variablen oder Nicht-Terminal­zeichen,
T das Alphabet der Terminal­zeichen,
 hierbei gilt: V Durchschnitt T =  leere Menge ;   ferner sei A = V vereinigt T das Gesamt­alphabet,
P enthalten in A+ × A* eine endliche Relation; die Elemente von P heißen Produktionen oder Ersetzungs­regeln,
S Element V eine spezielle Variable, das Startsymbol.

Durch die Produktionen oder Ersetzungs­regeln wird festgelegt, wie aus Wörtern w über dem Gesamt­alphabet A neue Wörter gebildet werden können. Eine Produktion wird auf ein Wort w angewendet, indem in w nach einem Vorkommen der linken Seite der Produktion gesucht wird und dieses Vorkommen durch die rechte Seite der Produktion ersetzt wird. Das Ergebnis ist ein Wort w'.

Beispiel:  Seien (S, ab) und (S, aSb) Produktionen und sei w = S. Indem in w die zweite Produktion auf S angewendet wird, ergibt sich als Ergebnis w' = aSb. Indem in w' = aSb die erste Produktion auf S angewendet wird, ergibt sich w'' = aabb.

Ableitung von Wörtern

Die Anwendung einer Produktion auf ein Wort w wird als Ableitungs­schritt bezeichnet. Wie im Beispiel angedeutet, können mehrere Ableitungs­schritte aufeinander folgen. Eine solche Folge von Ableitungs­schritten wird als Ableitungs­folge bezeichnet.

Die Menge aller Paare (w, w') von Wörtern, bei denen sich w' durch Anwendung einer Produktion, also durch einen Ableitungs­schritt aus w erzeugen lässt, bildet eine Relation  Pfeil nach rechts  auf A+ × A*.

Definition:  Sei G = (V, T, P, S) eine Grammatik und sei A = V vereinigt T. Die Relation P lässt sich in natürlicher Weise zu einer Relation  Pfeil nach rechts   enthalten in A+ × A* erweitern, indem für alle w, w' Element A+ definiert wird:

w Pfeil nach rechts w'   genau dann wenn    es existiert x, y Element A*,  (u, vElement Pw = xuy   und   w' = xvy

Es gilt also w Pfeil nach rechts w', wenn innerhalb des Wortes w ein Vorkommen der linken Seite u einer Produktion (u, v) durch die zugehörige rechte Seite v ersetzt wird und das Ergebnis das Wort w' ist.

Offen­sichtlich gilt auch u Pfeil nach rechts v für alle Produktionen (u, vElement P. Wir schreiben deshalb Produktionen auch in der Form u Pfeil nach rechts v.

Die Sprechweise für die Relation  Pfeil nach rechts  ist wie folgt: Das Wort w erzeugt direkt das Wort w' oder w' lässt sich aus w direkt ableiten oder w' ist direkt ableitbar aus w.

Die reflexive und transitive Hülle von  Pfeil nach rechts  ist die Relation  grammatikalische Ableitung . Es gilt w grammatikalische Ableitung w', wenn w' durch eine Ableitungs­folge, d.h. in 0 oder mehr Ableitungs­schritten, aus w ableitbar ist, (Sprechweise: w' ist ableitbar aus w oder w erzeugt w').

Erzeugung einer Sprache

Definition:  Die von einer Grammatik G = (V, T, P, S) erzeugte Sprache L(G) ist die Menge aller nur aus Terminal­zeichen bestehenden Wörter, die aus dem Startsymbol S ableitbar sind:

L(G)  =  { w Element T*  |  S grammatikalische Ableitung w }

 

Das folgende Beispiel ver­anschaulicht, wie ein Wort einer Sprache aus dem Startsymbol der Grammatik abgeleitet wird.

Beispiel:  Gegeben sei folgende Grammatik G = (V, T, P, S) mit

V = {S},   T = {a, b},   P = { S Pfeil nach rechts aSb, S Pfeil nach rechts ab }

Aus dem Startsymbol S lässt sich beispiels­weise aSb direkt ableiten; aus aSb lässt sich aaSbb direkt ableiten; aus aaSbb lässt sich aaabbb direkt ableiten (durch Anwendung der Produktion S Pfeil nach rechts ab).

Die Folge

S
 Pfeil nach rechts aSb
 Pfeil nach rechts aaSbb
 Pfeil nach rechts aaabbb

ist die Ableitungs­folge für aaabbb.

 

Die von G erzeugte Sprache ist

L(G)   =   { anbn  |  n Element natürliche Zahlen }   =   { ab, aabb, aaabbb, ... }

Im Folgenden fassen wir Produktionen mit gleicher linker Seite zu einer Produktion mit ver­schiedenen Alternativen als rechter Seite zusammen. Die beiden Produktionen aus dem vorigen Beispiel ergeben damit die Produktion

Sgeht über nachaSb  |  ab

Weitere Beispiele

Es folgen zwei weitere Beispiele für Grammatiken.

Beispiel:  Gegeben sei folgende Grammatik G = (V, T, P, S) mit

V = {S, X, Y},   T = {a, b}

und den Produktionen

Sgeht über nachXSY  |  ε
XYgeht über nachYX
Xgeht über nacha
Ygeht über nachb

 

Die Grammatik erzeugt die Sprache

L(G)   =   { w Element {a, b}*  |  |w|a = |w|b }

bestehend aus allen Wörtern, die gleich viele a's und b's enthalten.

Beispiel:  Gegeben sei folgende Grammatik G = (V, T, P, S) mit

V = {S},   T = {a, b}

und den Produktionen

Sgeht über nachaSa  |  bSb  |  ε

 

Die Grammatik erzeugt die Sprache

L(G)   =   { wwR  |  w Element {a, b}*,  wR ist das Spiegelbild von w }

der Palindrome1) gerader Länge über dem Alphabet {a, b}.

Aufgaben

Aufgabe 1:  Geben Sie jeweils eine Ableitungs­folge für das Wort abba in den Grammatiken aus dem vorigen Abschnitt an.

Aufgabe 2:  Entwerfen Sie eine Grammatik G = (V, T, P, S) für die Sprache

L  =  { w Element {a, b}*  |  w = wR }

aller Palindrome (gerader und ungerader Länge) über dem Alphabet {a, b}.

Aufgabe 3:  Entwerfen Sie eine Grammatik G = (V, T, P, S) für die Sprache

L  =  A*

aller Wörter über dem Alphabet A = {a, b}.

Aufgabe 4:  Beschreiben Sie informell mit Worten, welche Sprache durch eine Grammatik mit folgenden Produktionen erzeugt wird.

Sgeht über nachaX  |  a
Xgeht über nachaX  |  bX  |  a

Aufgabe 5:  

Die Grammatik mit den Produktionen

Sgeht über nachaSbS  |  ε

erzeugt die Sprache L(G) = { w  |  w stellt eine korrekt aufgebaute Klammer­struktur dar, wobei a einer öffnenden und b einer schließenden Klammer entspricht }

Geben Sie eine Ableitungs­folge für das Wort w = aababbab an.

Zusammenfassung

Mithilfe einer Grammatik und ihrer Produktionen lassen sich aus dem Startsymbol durch eine Folge von Ersetzungen Wörter erzeugen. Alle Wörter, die sich aus dem Startsymbol erzeugen lassen und die nur aus Terminal­zeichen bestehen, bilden die von der Grammatik erzeugte Sprache.


1)  Ein Palindrom ist ein Wort, das man vorwärts und rückwärts lesen kann, wie z.B. otto.

 

Weiter mit:  [Chomsky-Hierarchie der Grammatiktypen]   [Kontextfreie Grammatik]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2003   Updated: 29.10.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik