Für jede kontextfreie Sprache Lkf gilt:
h(R ∩ Dn) = Lkf.
|
Mit dem Satz von Chomsky-Schützenberger kann von einer Sprache gezeigt werden, dass sie kontextfrei ist.
Somit bietet dieser Satz mehr als das Pumpinglemma für kontextfreie Sprachen.
Zwar kann man damit korrekt zeigen, dass eine Sprache nicht mehr kontextfrei ist, falls aber die Eigenschaften des Pumpinglemmas gelten, ist dies noch kein Beweis, dass es sich tatsächlich um eine kontextfreie Sprache handelt.
Auch einige nicht-kontextfreie Sprachen erfüllen die Bedingungen des Pumpinglemmas.
Der Satz besagt nun, dass für jede kontextfreie Sprache Lkf ein regulärer Ausdruck R, eine Dycksprache Dn und einen Homomorphismus h existieren,
so dass h(R ∩ Dn) = Lkf.
D.h.: Wendet man den Homomorphismus auf die Schnittmenge von regulärem Ausdruck und einer entsprechenden Dycksprache an, so ergibt sich die betrachtete kontextfreie Sprache.
Wie das genau funktioniert und wie die einzelnen Bestandteile aufgebaut sind, wird in diesem Abschnitt beschrieben.
|
Prinzip
