|
| Für jede kontextfreie Sprache L gibt es eine Konstante n (aus dem Bereich der natürlichen Zahlen),
so dass sich jedes Wort z aus L, das mindestens so lang wie n ist, zerlegen lässt in z = uvwxy,
wobei gilt |vwx| =< n und |vx| >= 1,
und die Wörter uviwxiy (i ist eine natüliche Zahl) auch zu L gehören.
|
Das Schleifenlemma wird genutzt, um zu zeigen, dass eine Sprache nicht kontextfrei ist.
Beispiel Sprache L = {ajbjcj | j > 0}
Wir nehmen an, dass die Sprache kontextfrei ist.
Dann muss es die Schleifenlemmakonstante n geben.
Betrachtet man das Wort z = anbncn mit der Konstante n.
Nun muss es eine Zerlegung von z in uvwxyz geben, wobei u und x aufgepumpt werden können.
- Wegen |vwx| =< n kann vx nicht sowohl a's als auch c's enthalten, da sie mindestens n (b's) voneinander entfernt stehen.
- v (bzw. x) kann auch keine zwei verschiedenen Symbole enthalten, da beim Aufpumpen eine Abfolge wie z.B. abab entstehen würde.
- Liegt vwx vollständig in den a's so enthält das Wort beim Aufpumpen zwar noch die gleiche Anzahl b's und c's, allerdings eine davon verschiede Anzahl a's
(gleiches gilt auch für den Fall, dass v und x weggelassen werden)
- Für v und x aus b's oder c's bestehend wird ähnlich argumentiert.
- Eine ähnliche Ungleichverteilung ergibt sich auch für vx bestehend aus a's und b's
Die Aufteilung des Wortes führt an allen möglichen Stellen zum Widerspruch.
Somit kann geschlussfolgert werden, dass L nicht kontextfrei ist.
 Trifft auf eine Sprache die Eigenschaft des Schleifenlemmas zu, so bedeutet dies nicht, dass es sich bei der Sprache um eine kontextfreie handelt.
So gibt es für die kontextsensitive Sprache L2= {aibjckdl | mit i=0 oder j=k=l} eine Konstante n nach dem Schleifenlemma.
Shieber (1986) konnte mittels des Schleifenlemmas beweisen, dass natürliche Sprachen kontextsensitive Konstruktionen enthalten.
|
1
2
3
4
5
6
Übersicht: Sprachklassen
