Die Mathe-Redaktion [Home] - Neues auf einen Blick 03.07.2022 07:59 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » NIchtregularität einer Sprache mit dem Pumping-Lemma nachweisen
Autor
Universität/Hochschule J NIchtregularität einer Sprache mit dem Pumping-Lemma nachweisen
InWi
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.10.2002
Mitteilungen: 608
Wohnort: In de Näh vun Mannem
  Themenstart: 2004-04-13

Hallo zusammen, ich hab nochmal ne Aufgabe zum Pumping-Lemma versucht, vielleicht könntet ihr schnell drüberschauen und mir sagen ob das richtig ist. Also: \stopalign Zeigen Sie, dass folgende Sprache nicht regulär ist: L={0^k^3 \| k \el\ IN_0} Sei L_1 regulär, dann gibt es nach dem Pumping-Lemma ein n_0 \el\ IN, so daß für alle w \el\ L_1 ( abs(w) > n_0 ) und jede Zerlegung w=xyz für w gilt: 1) abs(xy) <= n_0 2) abs(y) >= 1 3) P:= {x y^k z \| k \el\ IN_0 } \subsetequal\ L_1 Sei w =0^n_0^3 mit x=0^i     y=0^(n_0 -i)     Z=0^(n_0^3 -n_0) mit i \el\ {0,...,n_0 -1} 1) abs(0^i * 0^(n_0 -i))= n_0 <= n_0 2) abs(0^(n_0 - i)) >= 1    weil i \el\ {0,...,n_0 - 1} 3) P:= {0^i 0^(k*n_0 - k*i) 0^(n_0^3 - n_0) \| k \el\ IN} \subsetequal\ L Zu zeigen, es gibt ein K \el\ IN_0, so daß für jedes n_0 \el\ IN und i \el\ {0,...,n_0 -1} gilt: 0^i 0^(k*n_0 - k*i) 0^(n_0^3 - n_0) \notel\ L dies ist genau dann erfüllt, wenn 0^(k*(n_0 -i)+1+n_0^3 -n_0) \notel\ {0^k^3 \| k \el\ IN} für k=n_0 ist dies der Fall, denn es gilt: n_0^3 < n_0^3+n_0 *(n_0 -i)+1<(n_0 +1)^3=n_0^3 + 3*n_0^2+3*n_0+1  da i \el\ {0,...,n_0-1} => P \nosubset\ L => Widerspruch zur Annahme => L regulär vielen Dank mfg florian [ Nachricht wurde editiert von InWi am 2004-04-13 12:54 ] [ Nachricht wurde editiert von InWi am 2004-04-13 12:59 ]

   Profil
lochi
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.08.2002
Mitteilungen: 1484
Wohnort: Allgäu
  Beitrag No.1, eingetragen 2004-04-13

Hallo InWi, das Prinzip stimmt, aber es sind genau die gleichen Macken drin wie in deinem anderen Thread. Schau dir da mal meinen letzten Post an und gib dann Bescheid, ob es klar ist. Viele Grüße, Lochi

   Profil
InWi
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.10.2002
Mitteilungen: 608
Wohnort: In de Näh vun Mannem
  Beitrag No.2, vom Themenstarter, eingetragen 2004-04-14

danke des müßte ich jetzt richtig haben - alle Unklarheiten sind beseitigt mfg florian

   Profil
InWi hat die Antworten auf ihre/seine Frage gesehen.
InWi hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]