Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kontextfreie Pumpeigenschaft und endliche Sprachen
Hallo.
Nachdem ich die VL komplett durchgearbeitet habe, bin ich nun hinsichtlich des kontextfreien Pumpinglemmas etwas verwirrt.
Jede endliche Sprache ist wie in der Uebung bewiesen trivialerweise auch regulaer. Es gibt also regulaere Sprachen, die endlich sind und deren Worte sich somit nicht beliebig aufpumpen lassen. Dann haetten sie aber ja die kontextfreie Pumpeigenschaft nicht, was aber ein Widerspruch ist, denn regulaere Sprachen sind eine echte Teilmenge der kontextfreien, welche alle die kfPE besitzen.
Ich habe mich etwas im Dschungel der Chomsky-Hierarchie verirrt, hoffentlich kann mir jemand ein wenig weiterhelfen. 
Genau darauf spielt das Beispiel
L = { {a}, {a, b} }
aus der Vorlesung an. L ist eine endliche Sprache und damit regulär, es ist auch recht einfach, eine reguläre Grammatik für L anzugeben.
Wollen wir zeigen, dass L die k.f. P.E. besitzt, so setzten wir n_L = 3 und sehen: Alle Wörter z aus L mit |z| <= n_L können in u, v, w, x, y, z = uvwxy zerlegt werden, so dass |vx| != leeres Wort, |vwx| <= n_L und \forall i \in N: uv^iwx^iy \in L, denn es gibt gar keine Wörter z mit |z| >= 3.
Man sieht, dass alle endlichen Sprachen die k.f. P.E. besitzen, man wählt einfach n_L = |längstes Wort| + 1.
Der Trick ist also einfach:
Man waehlt das nL so gross, dass die Menge der Woerter aus L mit Laenge >= nL die leere Menge ist und die geforderten Eigenschaften gelten, weil alle Aussagen ueber die Elemente der leeren Menge wahr sind?
1 „Gefällt mir“
So habe ich das verstanden.
1 „Gefällt mir“