Pumping-Lemma für kontextfreie < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:30 So 23.01.2011 | | Autor: | Loko |
| Aufgabe | Zeige mit Hilfe des Pumping-Lemmas für kontextfreie Sprachen, dass die Folgende Sprache nicht kontextfrei ist:
L = [mm] \{w \in \{a,b \}^{\*} | length(w) = n^{3}, n \in \IN \} [/mm] |
Ich habe die Aufgabe für eine andere Sprache hinbekommen [mm] (a^{i}b^{j}c^{i}d^{j}). [/mm] Bei dieser Sprache weiß ich aber nicht wie ich ein Wort der Länge [mm] n^{3} [/mm] konstruieren kann.
Unsere Definition für length(w) ist:
[mm] length(\lambda) [/mm] = 0
length(xv) = length(v) + 1 (x [mm] \in [/mm] A, v [mm] \in [/mm] A*)
Wenn ich jetzt nämlich versuche mit w = [mm] a^n^{2} b^{n} [/mm] etwas zu machen ist doch length(w) = 2n+n oder?
Viele Grüße
Loko
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 25.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
