Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in PUM-AL

Beantwortet: Warum wählt die Musterlösung in dem Fall "vx enthält kein a" i=0?

Wed, 22 Oct 2014 14:24:57 +0000

Warum wählt die Musterlösung in dem Fall "vx enthält kein a" i=0?

wenn vx kein a enthält, muss vx b und/oder c enthalten. Pumpt man mit i=0 fällt vx aus dem Wort, d.h. das Wort hat nach dem Pumpen weniger b und/oder weniger c -> da beim gewählten Wort die Anzahl a, b und c gleich ist, muss das gepumpte Wort also mehr a als b und/oder mehr a als c enthalten, weshalb das gepumpte Wort nicht in der Sprache sein kann (-> Widerspruch zur Annahme)

Kann man in dem Fall "vx enthält kein a" auch i>1 wählen?

Wenn du den Fall weiter aufspaltest zu "vx enthält nur b", dann hätte man mit i > 1 nach dem Pumpen mehr b als c und damit den Widerspruch. Dann müsstest du aber noch die beiden Fälle "vx enthält b und c" sowie "vx enthält nur c" behandeln. In diesen beiden Fällen bekommt man nach dem Pumpen mit i>1 zusätzliche c. Deshalb kann das Wort aber immernoch in der Sprache liegen, d.h. du wirst echte Probleme bekommen, den Widerspruch zu zeigen (meine Vermutung: es ist unmöglich). Mit i=0 ist das wesentlich einfacher.

Prinzipiell kannst du das i wählen, wie du willst. Um eine Pumpinglemma-Aufgabe zu lösen, kann es jedoch sein, dass manche Werte für i geschickter sind als andere. Wenn man i ungeschickt wählt, kann es sogar sein, dass man überhaupt keine Chance hat, zu zeigen, dass das gepumpte Wort nicht in der Sprache liegt.

Welches i man geschickterweise wählt, ist von der Aufgabe (und, falls man eine Fallunterscheidung macht, vom betrachteten Fall) abhängig.Eine gute Vorgehensweise, um ein geeignetes i zu finden, ist, sich zu überlegen, wie man das Wort (das man am Anfang der Aufgabe selber gewählt hat) verändern muss, damit es nicht mehr in der Sprache liegt.

Daher in der Musterlösung von PUM-AL in einem Fall i>1 und in dem anderen i=0 gewählt.

Gruß,

Tobias (Tutor)

Beantwortet: Alternative Beweisführung?

Wed, 22 Oct 2014 14:21:31 +0000

Hallo,

der Beweis ist nicht ausreichend, da nicht alle Zerlegungen des gewählten Wortes so aussehen, dass vwx nur aus a's besteht. Man muss immer alle möglichen Zerlegungen untersuchen, deshalb auch die Fallunterscheidung, die in der Summe wirklich alle möglichen Zerlegungen untersucht! Schau dir nochmal in den Folien an, was genau du zeigen musst.

Gruß,

Adam (Tutor)

Beantwortet: Frage zur Lösung: mehr a's als b's?

Wed, 22 Oct 2014 14:19:54 +0000

Ja, das heißt, dass a's als b's in dem Wort enthalten sind.

Wichtig ist in diesem Fall die Pumpvariable i=0. v0 und x0 ist jeweils das leere Wort, unabhängig, was auch immer für ein Wort v bzw. x ist. Man kann sich das informell so vorstellen: man schreibt null mal v bzw. x hintereinander.

Daher gehen b's und/oder c's "verloren", wenn man mit i=0 pumpt, während die Anzahl der a's unverändert bleibt (vx enthält kein a). Da das urprüngliche Wort z=anbncn genauso viele a's wie b's wie c's enthält, muss das mit i=0 gepumpte Wort mehr a's als b's bzw. c's enthalten.

Tobias (Tutor)