Pumping-Lemma: Nicht-Regularit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe ein Problem mit zwei Aufgaben:
1.) Zeigen Sie das die Sprache
[mm]L := \{z | z = 1^k[/mm] oder [mm]z = 0^j 1^{k^2} [/mm] für [mm] j >= 1 [/mm] und [mm] k >= 1 \}[/mm] 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 [mm]z = 1^n[/mm] mit [mm]|z| >= n[/mm] mit [mm]z = uvw[/mm], sodass z.B. u = leeres Wort, [mm]v = 1^j[/mm] und [mm]w = 1^{n-j}[/mm]. 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 [mm]z = 0^j 1^{k^2}[/mm], kann man [mm]n = j = k[/mm] wählen (ist ja nicht verboten, sowohl [mm]j >=1[/mm] als auch [mm]k >=1[/mm] gewählt werden darf). NUn wähle ich die Zerlegung [mm]u = 0^m, v = 0^{n-m}, uv = 0^n, w = 1^{n^2}[/mm]. 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
Danke schonmal,
LG Matze
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:38 Di 10.01.2012 | | Autor: | sandp |
> Hallo,
>
> ich habe ein Problem mit zwei Aufgaben:
>
> 1.) Zeigen Sie das die Sprache
> [mm]L := \{z | z = 1^k[/mm] oder [mm]z = 0^j 1^{k^2}[/mm] für [mm]j >= 1[/mm] und [mm]k >= 1 \}[/mm]
> 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 [mm]z = 1^n[/mm] mit [mm]|z| >= n[/mm] mit [mm]z = uvw[/mm], sodass z.B. u =
> leeres Wort, [mm]v = 1^j[/mm] und [mm]w = 1^{n-j}[/mm]. Wenn man v nun mit i
> >= 0 pumpt ist der entstehende Exponent immer = k >= 1 und
> somit wäre das Pumping-Lemma erfüllt.
>
Was wäre mit j = 0?
Normal darfst du keine Aussagen darüber machen wie viele Elemente in u enthalten sind, du weißt lediglich, dass |uv| =< n und |v| >= 1, aber du weißt nicht ob u leer ist
probier es doch mal mit k = 2n damit dürftest du keine Probleme haben
> Für das Wort [mm]z = 0^j 1^{k^2}[/mm], kann man [mm]n = j = k[/mm] wählen
> (ist ja nicht verboten, sowohl [mm]j >=1[/mm] als auch [mm]k >=1[/mm]
> gewählt werden darf). NUn wähle ich die Zerlegung [mm]u = 0^m, v = 0^{n-m}, uv = 0^n, w = 1^{n^2}[/mm].
> 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.
gleiches Problem wie oben
>
> 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
am Besten schreibst du mal die komplette Aufgabenstellung hier rein, dann kann ich dir besser helfen, da ich die Aufgabe sehr seltsam finde, da man das Pumping-Lemma normalerweiße nur benutzt um zu zeigen, dass eine Sprache nicht Regulär ist, die andere Richtung ist NICHT möglich, wahrscheinlich sollst du das bei dieser Aufgabe lernen.
>
> Danke schonmal,
>
> LG Matze
|
|
|
|
