Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Pumping Lemma 2 (http://www.informatikerboard.de/board/thread.php?threadid=128)
Geschrieben von foogi am 14.01.2007 um 19:35:
Pumping Lemma 2
hallo,
nach dem Beitrag vom Pumping Lemma, habe ich nun dazu weitere Fragen.
1. Kann ich nachdem selben Prinzip wie im vorigen Beitrag mit allen Sprachen umgehen? oder nach was muss ich mich da genau richten.
Beispiel:
wie würde ich diese Aufgabe denn richtig angehen? Denn wenn ich nach dem Prinzip vom vorigen Beitrag vorgehe, so komme ich irgendwie nicht auf die Lösung? oder?
L={a^k b^k| k>=1}
wenn ich nun als Wort 2n wähle, |x| >=n
dann zerlege ich das wort x= uvw in
u = x^q
v= x^r
w=x^s
2n = q+r+s
wegen |uv|<=n und |v|>=1 gilt ja 1<=r<=n
wenn ich nun aufpumpe, so habe ich
2n<|2n +r|<=2n+n
das nächste Wort wäre doch dann 2n+2, bei n=1 wäre es nicht enthalten,
ab n=2 aber schon??
Was habe ich nun falsch gemacht?
Danke
Geschrieben von Tobias am 14.01.2007 um 20:17:
Dein Beweis geht garnicht auf die Sprache ein.
Deine Zerlegung ist quatsch, denn das x hat nichts mit der Sprache zu tun. Deine anschließende Argumentation ist auch total konfus.
Wenn ein n existiert, so muss ein Wort der Länge 2n natürlich auch eine aufpumpbare Zerlegung haben.
Das Wort sieht dann so aus:
Die Zerlegung ist ja dann auch klar:
Wegen
muss
mit
sein.
Kommst du nun weiter?
Geschrieben von Tobias am 15.01.2007 um 19:36:
Zitat: |
wenn ich nun als Wort 2n wähle, |x| >=n
dann zerlege ich das wort x= uvw in
u = x^q
v= x^r
w=x^s |
Du zerlegst x in
????? Das ist doch offensichtlich Quatsch.
Du musst
zerlegen, daher für u, v und w Teilwörter von a^nb^n angeben.
Wenn aber
und
dann muss doch schon eine Aussage über u und v zu treffen sein. (Siehe vorheriger Beitrag)
Forensoftware: Burning Board, entwickelt von WoltLab GmbH