Informatiker Board | Druckvorschau: Zeigen Sie das die Sprache L das Pumpinglemma erfüllt

Geschrieben von gast23212 am 08.01.2012 um 21:03:

Zeigen Sie das die Sprache L das Pumpinglemma erfüllt

Meine Frage:
Hallo,

ich habe ein Problem mit zwei Aufgaben:

1.) Zeigen Sie das die Sprache
$[latex]L := \{z | z = 1^k[/latex]$ oder $[latex]z = 0^j 1^{k^2} [/latex]$ für [latex] j >= 1 [/latex]

und $[latex] k >= 1 \}[/latex]$ das Pumping-Lemma erfüllt. L kann man ja aufteilen in La vereinigt mit Lb.

Ist es richtig, das ich zeigen muss das beide Wörter in einer beliebigen Zerlegung der Wörter pumpbar sein müssen? Also das das Pumping-Lemma erfüllt ist für eine beliebige Zerlegung der Wörter?

2.) In der 2. Aufgabe soll ich zeigen das die Sprache von Aufgabe 1 nicht regulär ist, d.h. ich muss für beide Teilsprachen La und Lb, wo La das erste Wort erzeugt und Lb das 2. Wort erzeugt, annehmen sie sind regulär (was daraus folgt das reguläre Sprachen unter Vereinigung abgeschlossen sind) und dies mit der 3ten Bedingung des Pumping-Lemmas zum Widerspruch führen, wobei hier ausreicht nur für eine Teilsprache zu zeigen das sie nicht regulär ist?

Meine Ideen:
Idee zu 1)
Also [latex]z = 1^n[/latex]

mit

mit

, sodass z.B. u = leeres Wort, [latex]v = 1^j[/latex]

und

. Wenn man v nun mit i >= 0 pumpt ist der entstehende Exponent immer = k >= 1 und somit wäre das Pumping-Lemma erfüllt.

Für das Wort $[latex]z = 0^j 1^{k^2}[/latex]$ , kann man [latex]n = j = k[/latex]

wählen (ist ja nicht verboten, sowohl [latex]j >=1[/latex]

als auch

gewählt werden darf). NUn wähle ich die Zerlegung $[latex]u = 0^m, v = 0^{n-m}, uv = 0^n, w = 1^{n^2}[/latex]$ . Egal wie ich v pumpe (beliebiges i), der Exponent der 0 des Wortes ist immer >= 1, damit ist auch hier das Pumping-Lemma erfüllt.

Ist diese Vorgehensweise korrekt?

Idee zu 2)

Also ich wähle wieder ein Wort mit Abhängigkeit von n (Pumping-Zahl), aber betrachte diesmal für dieses Wort alle möglichen Zerlegungen, sobald alle dieser Zerlegungen unter Pumpen sagen,dass das Wort nicht mehr zur Sprache gehört, dann ist das ein Widerspruch und meine als regulär angenommene Sprache ist nicht mehr regulär