next up previous contents index
Next: Das Pumping Lemma (uvwxy-Theorem) Up: Kontextfreie Sprachen (Typ 2) Previous: Kontextfreie Sprachen (Typ 2)   Contents   Index

Subsections


Normalformen 52

Für die Normalformen müssen folgende Regeln gelten (durch Umformungen erreichbar):


Chomsky Normalform 53

Zu jeder kontextfreien Grammatik $ G$ mit $ \varepsilon\notin L\left(G\right)$ existiert eine Chomsky Normalform (CNF). Die Chomsky Normalform liegt vor, wenn alle Regeln eine der folgenden Formen haben:

Ist $ w\in L\left(G\right)$, so gilt:

$\displaystyle S\Rightarrow_{G}^{2\left\vert w\right\vert-1}w$

Ein Algorithmus für die Umformung findet sich im Buch (vorher Kettenregeln, und $ \varepsilon$-Regeln entfernen!)


Greifenbach Normalform 54

Zu jeder kontextfreien Grammatik $ G$ mit $ \varepsilon\notin L\left(G\right)$ existiert eine Greifenbach Normalform. Diese liegt vor, wenn alle Regeln eine der folgenden Formen haben:

Die Greifenbach Grammatik ist eine Erweiterung der regulären Grammatik, dort wäre nur $ k=0$ und $ k=1$ zugelassen.

Ein Algorithmus für die Umformung findet sich im Buch.


next up previous contents index
Next: Das Pumping Lemma (uvwxy-Theorem) Up: Kontextfreie Sprachen (Typ 2) Previous: Kontextfreie Sprachen (Typ 2)   Contents   Index
Marco Möller 18:11:27 24.10.2005