Pumpinglemma

Neue Frage »

Hellboy256 Auf diesen Beitrag antworten »
Pumpinglemma
Man soll anhand der Kontraposition des Pumpinglemmas beweisen, dass L={(a^n)(b^n)(c^n) | n>=0} nicht regulaer ist.
papahuhn Auf diesen Beitrag antworten »
RE: Pumpinglemma
Man dankt für die Information.

Konkrete Fragen?
Hellboy256 Auf diesen Beitrag antworten »
RE: Pumpinglemma
Meine Konkrete Frage:
Wie der Beweis geht!
Dunkit Auf diesen Beitrag antworten »

Hast du denn die Aussage des PL verstanden? Also was genau die drei Bedingungen bedeuten?
Hellboy256 Auf diesen Beitrag antworten »

Also wenn ich zunaechst
ein n el IN (z.B. n=5) und
einen String w=abbccc
sodass gilt l(w)>=n (6>5)
Zerlegung von w in Teilwoerter w=xyz mit l(xy)<=n.
So existiert ein k el IN mit x(y)^k z welches kein Element mehr aus L ist.

Wenn ich jetzt fuer die Zerlegung von w
w=(a)(bbc)(cc) waehle, so gilt fuer ein beliebiges k nicht mehr, dass x(y)^k z Element aus L ist.
Stimmt das so?

Nun soll der Beweis anhand der Kontraposition des Pumpinglemmas als Spiel durchgefuehrt werden:

1. Spieler 1 waehlt eine Sprache L
2. Spieler 2 waehlt ein beliebiges n.
3. Spieler 1 waehlt ein Wort w el L, l(w)>=n
4. Spieler 2 zerlegt w beliebig in 3 Teile x,y,z sodass l(xy)<=n. Spieler 2 muss die Zerlegung nicht mitteilen
5. Spieler 1 gewinnt, wenn er k waehlen kann, sodass x(y)^k z kein element aus L ist.
L ist genau dann nicht regulaer, wenn Spielerin 1 immer gewinnt

Also wenn ich das einfach mal durchgehe:
1. Sprache L={(a^n)(b^n)(c^n) | n>=0}
2. n=5
3. abbccc
4. (a)(bbc)(cc)
5. Wenn Spieler 1 immer gewinnt (Beweis durch Induktion??):
k=2 => abbcbbccc kein element der angegebenen Sprache
k=n => a((bbc)^n)cc
k=n+1 => a((bbc)^(n+1))cc = a(((bbc)^n)bbc)cc was auch kein element der Sprache L ist

Stimmt das so??
Dunkit Auf diesen Beitrag antworten »

Was ich nicht ganz verstehe: Das Wort abbccc, was du die ganze Zeit benutzt, ist garnicht in der Sprache!
Ansonsten ist die Idee nicht verkehrt, sich ein Wort aus der Sprache zu suchen und zu zeigen, dass dieses keine Zerlegung besitzt, die die Forderungen im PL erfüllt...
 
 
Hellboy256 Auf diesen Beitrag antworten »

Achso das n ist ja bei allen gleich, dann die Sprache w=aabbcc => w=xyz => w=(a)(ab)(bcc)

Wuerde mit diesem Wort mein Beweis fuer die Kontraposition des Pumpinglemmas als Spiel, so wie ich ihn hingeschrieben hab stimmen?
Dunkit Auf diesen Beitrag antworten »

Nicht ganz.

Du nimmst dir ein n, für das das PL gelten soll.

Dann nimmst du das Wort . Hier soll es eine Zerlegung in geben. Was weißt du aber über das Teilwort ?
Hellboy256 Auf diesen Beitrag antworten »

dass l(xy)<=n sein muss
Dunkit Auf diesen Beitrag antworten »

Richtig. Wenn das Wort, was wir betrachten wollen aber ist, was heißt das für und damit insbesondere für ?
Hellboy256 Auf diesen Beitrag antworten »

wenn ich sage dass x+y<=n sein muessen,
dann das y<=n-x sein muss?
Dunkit Auf diesen Beitrag antworten »

Nein vorsicht, x und y sind hier Worte. Nur die LÄNGE von xy ist kleiner als n. Aber wie sieht das Teilwort xy denn aus?
Hellboy256 Auf diesen Beitrag antworten »

Sorry da heng ich im Moment etwas...
Dunkit Auf diesen Beitrag antworten »

Naja
, und folglich ist mit . Das wiederum heißt aber , wobei da ja eine Bedingung im PL ist. So und das kannst du jetzt ausnutzen...
Hellboy256 Auf diesen Beitrag antworten »

Koennte ich dann jetzt sagen, dass wenn
xy = a^i und
y=a^(i-|x|) dass
x = a^(i-|y|) und

w = a^(i-|y|) (a^(i-|x|)^k z
und bei w jetzt die Induktion ueber k machen?
Dunkit Auf diesen Beitrag antworten »

Ich glaube du hast noch nicht so recht verstanden, wie du das PL nutzen kannst, daher hier die Lösung:

Du weißt, dass egal wie du das Wort zerlegst in (sofern du bei der Zerlegung die Vorgaben aus dem PL einhälst; siehe oben), immer sein wird und .
Nach dem PL müsste es eine Zerlegung geben, sodass für jedes immernoch ein Wort deiner Sprache ist. In unserem Fall ist aber z.B. für das "neue" Wort , also hat das Wort weniger a's als b's und c's und damit ist das Wort nicht in . Da reguläre Sprachen das PL erfüllen, kann also nicht regulär sein!
Neue Frage »
Antworten »



Verwandte Themen