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

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Zeigen Sie das die Sprache L das Pumpinglemma erfüllt » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 3 Beiträge
KarlitosbesterFreund	Mathe Prof Level: Profi Danke Karlito dein Beitrag hat mir sehr geholfen und weitergebracht
Karlito	In Automatentheorie bin ich leider nicht so fit. Deshalb kann ich hier nicht helfen... Gruß, Karlito
gast23212	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 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 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 $[latex]z = 0^j 1^{k^2}[/latex]$ , kann man wählen (ist ja nicht verboten, sowohl 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