Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping Lemma 2

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Pumping Lemma 2

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

Pumping Lemma 2

Zitatantwort auf diesen Beitrag erstellen

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

14.01.2007 19:35

Nehmen Sie foogi in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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: [latex]a^nb^n[/latex]

Die Zerlegung ist ja dann auch klar:

Wegen $[latex]|uv| \leq n[/latex]$ muss [latex]uv = a^r[/latex]

mit $[latex]r \leq n[/latex]$ sein.

Kommst du nun weiter?

14.01.2007 20:17

Nehmen Sie Tobias in Ihre Freundesliste auf

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

Zitat:

Original von Tobias
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: [latex]a^nb^n[/latex]

Die Zerlegung ist ja dann auch klar:

Wegen $[latex]|uv| \leq n[/latex]$ muss [latex]uv = a^r[/latex]

mit $[latex]r \leq n[/latex]$ sein.

Kommst du nun weiter?

mit dem x meinte ich das die Wortlänge größer gleich n sein muss, wenn ein Pumping Lemma existiert. Und die länge von n kann man doch selber wählen, dachte ich, deswegen 2n. wenn ich 2n einsetze, so ist das Wort länger als n.

Die Zerlegung ist mir nicht ganz klar verwirrt

das Wort sollte man doch immer in 3 Teile zerlegen können? oder nicht?

15.01.2007 15:42

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 [latex]x^qx^rx^s[/latex]

????? Das ist doch offensichtlich Quatsch.

Du musst

[latex]x = a^nb^n = uvw[/latex]

zerlegen, daher für u, v und w Teilwörter von a^nb^n angeben.

Wenn aber [latex]uvw = a^nb^n[/latex]

und $[latex]|uv| \leq n[/latex]$ dann muss doch schon eine Aussage über u und v zu treffen sein. (Siehe vorheriger Beitrag)

15.01.2007 19:36

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping Lemma 2