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.)

alternativer Beweis

0 Punkte
48 Aufrufe

Hallo,

wäre es auch möglich, das Pumping-Lemma folgendermaßen zu begründen:

a)vx enthält nur a's oder b's wie in der Lösung

b)vx enthält a's und b's :

hier gehen wir wie in der Begründung der Aufgabe 69 vor, und zwar :

für jedes gepumpte a muss zusätzlich k b's entstehen (da lzlb = (lzla)^2=k. lzla) also :

vx muss entweder leer sein (Widerspruch zu lvxl>=1)

oder vx muss mindestens 1+k Zeichen enthalten (Widerspruch zu lvwxl=<k)

Gefragt 4, Jan 2017 in PUM-AH von uuehc uuehc Lernwillige(r) (860 Punkte)  

Eine Antwort

+3 Punkte
 
Beste Antwort

Ich gehe mal davon aus, dass du von Wort $w=a^kb^{k^2}$ und $i=2$ ausgehst.

Dann ist deine Aussage "für jedes gepumpte a muss zusätzlich k b's entstehen" falsch. Beispiel: $w=a^2b^4$ ->k=2 -> gepumptes Wort $a^3b^9$ -> es müssen 5 b's entstehen und nicht 2

Für ein gepumptes a müssen zusätzlich $2k+1$ b's entstehen, für zwei gepumpte a's müssen zusätzlich $4k+4$ b's entstehen, für 3 müssen $6k+9$, ...

D.h. für jedes gepumpte a müssen mindestens $2k+1$ b's entstehen.

Jetzt kann man die Argumentation wie in Aufgabe 69 verwenden:

vx muss entweder leer sein -> Widerspruch
oder vx muss mindestens $2k+2$ Zeichen enthalten -> Widerspruch

Viele Grüße Philipp (Tutor)

 

Beantwortet 4, Jan 2017 von ugehd ugehd Tutor(in) (106,130 Punkte)  
ausgewählt 5, Jan 2017 von Lukas König
...