Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

–1 Punkt
51 Aufrufe

Hallo,

kann ich in diesem Beispiel  sagen, wenn   vx kein a enthält  dann wähle ich  i>1?

wenn nicht...warum soll ich dann in diesem Fall i=0 auswahlen?

Danke für die Antwort

 

Gefragt 22, Okt 2014 in PUM-AL von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte

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 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...