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
oder
für
und
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
mit
mit
, sodass z.B. u = leeres Wort,
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
, kann man
wählen (ist ja nicht verboten, sowohl
als auch
gewählt werden darf). NUn wähle ich die Zerlegung
. 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