Theoretische Informatik

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

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'.

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  →  auf A⁺ × A*.

Offen­sichtlich gilt auch u → v für alle Produktionen (u, v) ∈ P. Wir schreiben deshalb Produktionen auch in der Form u → v.

Die Sprechweise für die Relation  →  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  →  ist die Relation   . Es gilt w  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

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

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

S

aSb  |  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

S		XSY  |  ε
XY		YX
X		a
Y		b

 

Die Grammatik erzeugt die Sprache

L(G)   =   { w ∈ {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

S

aSa  |  bSb  |  ε

 

Die Grammatik erzeugt die Sprache

L(G)   =   { ww^R  |  w ∈ {a, b}*,  w^R ist das Spiegelbild von w }

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

Aufgaben

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

S		aX  |  a
X		aX  |  bX  |  a

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.