Pumpinglemma |
09.06.2010, 18:13 | Hellboy256 | Auf diesen Beitrag antworten » |
Pumpinglemma |
||
09.06.2010, 21:18 | papahuhn | Auf diesen Beitrag antworten » |
RE: Pumpinglemma Man dankt für die Information. Konkrete Fragen? |
||
09.06.2010, 22:26 | Hellboy256 | Auf diesen Beitrag antworten » |
RE: Pumpinglemma Meine Konkrete Frage: Wie der Beweis geht! |
||
09.06.2010, 22:57 | Dunkit | Auf diesen Beitrag antworten » |
Hast du denn die Aussage des PL verstanden? Also was genau die drei Bedingungen bedeuten? |
||
10.06.2010, 11:12 | 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?? |
||
10.06.2010, 13:47 | 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... |
||
Anzeige | ||
|
||
10.06.2010, 14:31 | 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? |
||
10.06.2010, 14:34 | 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 ? |
||
10.06.2010, 14:37 | Hellboy256 | Auf diesen Beitrag antworten » |
dass l(xy)<=n sein muss |
||
10.06.2010, 14:40 | 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 ? |
||
10.06.2010, 14:43 | Hellboy256 | Auf diesen Beitrag antworten » |
wenn ich sage dass x+y<=n sein muessen, dann das y<=n-x sein muss? |
||
10.06.2010, 14:45 | 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? |
||
10.06.2010, 14:48 | Hellboy256 | Auf diesen Beitrag antworten » |
Sorry da heng ich im Moment etwas... |
||
10.06.2010, 14:54 | 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... |
||
10.06.2010, 15:03 | 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? |
||
10.06.2010, 21:49 | 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! |
|