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.
Pumpen kontextfreier Sprachen im Schöning
In meinem Schöning steht nach dem Pumplemma für kontextfreie Sprachen eine Beispiel, bei dem es um die Sprache a^m b^m c^m geht. Schöning schreibt da in dem Beispiel (Seite 61 bei mir), dass die vwx Zerlegung wegen der Längenbeschränkung sich nicht über den gesamten Bereich der b erstrecken kann. Wieso? Laut Pumplemma darf vwx kleiner gleich Pumpzahl sein. Der Fall Anzahl der b = Pumzahl, also vwx erstreckt sich nur über “b” sollte also damit auch abgedeckt sein. Wieso sagt er, das ginge nicht? Kann mich mal jemand aufklären? :rolleyes:
Bei meinem Busen: Klar kann vwx nur aus b’s bestehen. Was er sagt ist, dass wegen |vwx|<=n kann sich vwx nicht über diesen bereich hinweg erstrecken. Um anständig pumpen zu können, müßte aber genau das möglich sein, schließlich müssen a’s, b’s und c’s um den gleichen faktor zunehmen, sprich vwx muss a’s, b’s UND c’s enthalten. Das ist alles was er damit meint, vwx könne “sich nicht über den gesamten bereich der b’s hinweg erstrecken”.