Datenverarbeitende Systeme
Kapitel 4: Formale Sprachen

4.1 Produktionen

Definition: Unter einer Grammatik G über einem Alphabet T verstehen wir eine Sammlung von Objekten G=(N,T S,P), wobei

N: Alphapet aller nichtterminalen Symbole z.B. { A, B, C, ... Z }

T: Alphapet aller terminalen Symbole z.B. { a, b, c, ... z }

S: Startsymbol der Grammatik

P: Die Menge aller Produktionen

Die Produktionen legen fest, welche Folge von Symbolen aus N und T wir auf welche anderen Symbole aus N und T abbilden dürfen. Dabei kann auch auf das leere Symbol € abgebildet werden. Auch ist es möglich, dass eine Folge auf verschiedene andere Abgebildet (produziert) werden kann.

Beispiel:
Wir nehmen ein Alphabet X={a,b} und einen regulären Ausdruck R=(ab)*bb*. Wörter aus der Sprache L(R) wären zum Beispiel ababbb, b, abb und so weiter. Eine zugehörige Grammatik wäre zum Beispiel N = {A,B,S}, T=X={a,b}, P = { ( S, AbB), ( A, abA ), ( A, € ), ( B, bB ), ( B, € ) } und G = ( N, T, S, P ).

Wie erzeugen wir damit zum Beispiel das Wort ababbb? Wir beginnen mit dem Startsymbol S und wenden die verfügbaren Produktionen so der Reihe nach auf S an, bis das gewüschte Wort entstanden ist. Aus S machen wir zunächst AbB, ersetzten dann das A durch abA und erhalten abAbB. Nochmals ersetzen wir A durch abA und dann A durch €. Wir haben dadurch das Wort ababB erzeugt. Zweimal ersetzen wir jetzt B durch bB und dann B durch € und erhalten so ababbb. Fertig.

4.2 Chromsky-Hirarchie

In einer Chromsky-Hirarchie gibt es verschiedene Bedingungen, die von den Produktionen einer Grammatik erfüllt werden müssen:

Grammatiken vom Typ 0 heißen Allgemeine Grammatiken und Bezeichnen ALLE Grammatiken (Wiederholungsfehler, Anm. d. Grundschullehrers)

Für Typ 1 gillt, dass nicht auf das leere Symbol € produziert werden darf. Außerdem muss auf eine Folge µ0 auf eine Folge µ1 abgebildet werden, die länger ist als µ0, mindestens jedoch gleich lang (|µ0| <= |µ1|). Wir sprechen dann von nichtverkürzenden Grammatiken.

Grammatiken vom Typ 2 enthalten alle Regeln für Typ 1 und gleichzeitig darf µ0 nur aus nichtterminalen Symbolen bestehen. Es darf nicht auf die terminalen Symbole in der Umgebung eines zu prozuierenden Symbols (oder einer Folge) ankommen. Diese Grammatiken heißen kontextfreie Grammatiken.

Legt man weiter fest, dass zusätlich nur auf Folgen abgebildet wird, die aus terminalen Symbolen bestehen und wahlweise auf maximal ein nichtterminales Symbol enden, so erhalt man (rechts) lineare Grammatiken vom Typ 3

4.3 Reguläre Sprachen

Satz:Eine Grammatik G heißt links linear, wenn alle Produktionen die Form A --> Bx haben, wobei B auch leer sein kann, nicht jedoch x! Dann ist die Klasse der Sprachen, die durch links lineare Grammatiken erzeugt werden die selbe, die auch durch rechts lineare Grammatiken erzeugt werden. Rechts lineare Grammatiken sind von der Form A --> xB.

Folgende Tabelle zeigt, wie man rechts lineare Grammatiken in links lineare umwandelt:

rechts linear	links linear
S --> tA	A --> t
S --> t	S --> t
A --> tB	B --> At
A --> t	S --> At

Formale Sprachen L heißen genau dann regulär, wenn es eine lineare Grammatik G mit L = L(G) gibt.

4.4 Kontextfreie Sprachen

Beispiel: Sei durch S ==> SS ==> Sb ==> SSb ==> Sbb ==> abb eine Ableitung des Wortes x = abb aus der Grammatik G = ( {S}, {a,b}, S, {S-->SS, S-->a, S-->b} ). Eine Ableitung ist also die Darstellung eines Wortes x aus G durch Rückführung auf die nötigen Produktionen, mit denen man vom Startzustand S aus zu x gelangt.

Jeder Ableitung von x aus einer kontextfreien Sprache kann ein Strukturbaum zugeordnet werden:

Eine kontextfreie Sprache L heißt eindeutig, falls es eine eindeutige Grammatik gibt, die L erzeugt. Alle regulären Sprachen sind eindeutig. Nicht alle kontextfreien Sprachen sind eindeutig.

Es gellten folgende Sätze:

Verschiedene Ableitungen des selben Wortes können den selben Strukturbaum haben
Verschiedene Ableitungen des selben Wortes können verschiedene Strukturbäume haben
Einer Ableitung eines Wortes können verschiedene Strukturbäume zugeordnet sein

Definition:Eine Ableitungsfolge S ==> x1 ==> x2 ==> ..... ==> xn = x heißt links-kanonisch (rechts-kanonisch), wenn in jedem Ableitungsschritt das am weitesten links (rechts) stehende nichtterminale Symbol durch ein terminales Symbol ersetzt wird. Eine kontextfreie Grammatik G jeißt eindeutig, wenn einem Wort x der Sprache nur ein Strukturbaum zugeordnet werden kann. Ansonsten nennen wir sie mehrdeutig.

Zu einer mehrdeutigen Grammatik G kann es eine äquivalente Grammatik G´ geben, die eindeutig ist. Dies muss aber nicht so sein. Ein Beispiel für die Existenz einer äquivalenten Grammatik (ich betrachte nur die Produktionen für Sprachen aus den Symbolen a und b mit einem einzigen nichtterminalen Symbol S): P(G) = { S --> SS | a | b } ist mehrdeutig. Dagegen ist P(G´) = { S --> aS | bS | a | b } äquivalent zu G und eindeutig.

Gibt es eine eindeutige Grammatik G, so ist die daraus erzeugt Sprache L kontextfrei. Reguläre Sprachen sind eindeutig. Es gibt allerdings kontextfreie Sprachen, die nicht eindeutig sind.

Analog zum Pumping-Lemma, mit dem wir nachweisen können, dass eine Sprache nicht regulär ist (nicht von einem endlichen Automaten erkannt wird), gibt es für kontextfreie Sprachen ein Pumping-Theorem. Der Nachweis, dass eine Sprache L nicht kontextfrei ist, gelingt wie folgt:

Das Pumping-Theorem

Das Pumpin-Theorem ist die mächtige Variante des gleichnamigen Lemmas. Es geht wie folgt (sei L nicht kontextfrei):
Für alle n aus N gibt es ein Wort z aus L mit |z| >= n. Dann gilt für alle Zerlegungen z=uvwxy mit |vwx| <= n und |vx| >= 1, dass es ein Wort z´=uvⁱwxⁱy gibt, das nicht zu L gehört.

Vorsicht: Wir müssen den Beweis für JEDE MÖGLICHE Zerlegung von z zeigen. Dazu wird eine Fallunterscheidung benötigt, die Aussagen macht, wie das Wort innerhalb der Zerlegung angeordnet sein kann. Dabei hilft uns insbesondere die Beschränkung, dass |vwx| nicht größer als n und |vx| mindestens eins ist. In der Regel haben wir symmetrische Verteilung (w teilt das Wort in der Mitte) und asymmetrische Verteilung (y = e oder u = e) zu unterscheiden. Jede Zerlegung muss ein Wort z´ liefern, dass nicht mehr in L liegt.

Auch hier können wir keinen Nachweis erbringen, das eine Sprache kontextfrei ist, wenn das Theorem nicht erfüllt ist. Wir müssen uns als Beweis wieder einen Automaten bauen, der eine kontextfreie Sprache erkennen kann. Ein solcher ist der im nächsten Kapitel vorgestellte Kellerautomat.