Nachweis der Regularität - Pum < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:14 Mo 10.03.2008 | | Autor: | Haase |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | | Ich soll mit Pumping Lemma beweisen das {0^n | n ist Kubikzahl} keine reguläre Sprache ist. |
Guten Tag Allerseits,
wäre super wenn Ihr mir helfen könntet.
Wenn ich n = 8 nehme und damit ist das Wort 0^8 = 0...0
und x,y,z existiert mit y != epsilon, |xy| <=n, k>=0
sei k =? dann ist w' = xy^(k)z = 0...0 }8+|y| = länge von 0...0 was ist dann z?
Ist jetzt schon ein Widerspruch, da z hier nicht zugeteilt werden kann? Oder ist |z| = 0 und damit müsste |y| = -8 werden und damit ist der Widerspruch da |y| nicht negativ werden darf?
Nebenbei: Wie ist das mit dem xyz, wie werden die immer zugeteilt? Und muss man ein k wählen?
Vielen Dank im Voraus
Gruß Haase
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 10:25 Di 11.03.2008 | | Autor: | Haase |
Jetzt habe ich es glaub ich verstanden.
Also wenn ich L = [mm] {0^n 1^n |n>=1} [/mm] habe
dann ist der Widerspruch mit w=xyz da mit:
0.....0 1.....1
n+|y| z
Widerspruch: Es gibt mehr 0en als 1en.
2ter Widerspruch: |y| darf nicht 0 werden?, richtig?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Do 13.03.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Mi 12.03.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
