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

Schöne Ferien!
 

 

Pumping Lemma- alternative Begründung richtig?

+2 Punkte
121 Aufrufe
Wäre es auch möglich hier bei der Begründung das Pumpwort $w =111$ zu wählen, dieses in
 
$xy = 1^j$, $y = 1^k$, $x = 1^{j-k}$ und $z = 1^{n-j}11$ für $0 < k \leq j \leq n$
 
zu zerlegen und mit $i = 0$ zu pumpen, sodass das Wort $w' = 1^{n-k}11$ entsteht, welches nicht element $L_3$ ist, da w^|w| gelten muss?
 
Danke im Voraus!
Gefragt 30, Jan 2016 in 2014-N-03 von uwduw uwduw Lernwillige(r) (1,230 Punkte)  
Bearbeitet 30, Jan 2016 von Lukas König

Eine Antwort

+1 Punkt

Nein, das geht nicht, denn Ihr Wort hat nicht die Länge $|w|\geq n$. (Das ist sehr wichtig und ein häufiger Fehler, bitte beachten Sie das in der Klausur!)

Außerdem dürfen Sie die Zerlegung nicht wählen, sondern müssen über alle möglichen Zerlegungen argumentieren!


Viele Grüße

Lukas König

Beantwortet 30, Jan 2016 von Lukas König Dozent (10,065,100 Punkte)  
und wenn ich das Pumpwort 1^n1^n1^n wähle? und den beweis dann äquivalent wie in den tuts führe mit Pumpvariable i=0 ?

y=1^k x=1^j-k xy=1^j mit 0<k<=j<=n
und daraus z=1^n-j1^n1^n

dann mit i=0 pumpen => w= 1^n-k 1^n1^n und das ist kein Element von L
Wie soll das denn gehen, $1^n1^n1^n$ ist doch nicht für alle $n$ in $L$! Gleich für $n=2$ gilt $111111 \notin L$.
Bitte schauen Sie sich das Pumping-Lemma nochmal gründlich an.
...