Pumping Lemma nutzlos?
Hi, ich verstehe den Sinn hinter dem Pumping Lemma nicht. Es soll ja dazu benuzt werden um zu zeigen das eine Sprache die eine Wortlänge größer oder gleich n ist nicht regulär ist.
Aber man kann mittels des Pumping Lemmas auch sehr häufig Sprachen die nicht regulär sind mittels Pumping Lemma als akzeptierte Sprache darstellen. Und andersrum kann man auch Sprachen die regulär sind sehr häufig als irregulär darstellen.
Das Pumping Lemma ist ja dann fast komplett nutzlos oder verstehe ich da etwas falsch?
1 Antwort
Und andersrum kann man auch Sprachen die regulär sind sehr häufig als irregulär darstellen.
Nein?
Das Pumpinglemma ist für alle regulären Sprachen gültig.
Und das Lemma ist nützlich, um bei manchen Sprachen zeigen zu können, dass die nicht regulär sein können. Es geht zwar nicht bei jeder nicht regulären Sprache, aber wenn es geht, kann man es leicht zeigen.
Das Pumpinglemma ist halt nur ein notwendiges Kriterium. Es gibt auch das Myhill-Nerode Theorem, welches eine notwendiges und hinreichendes Kriterium für reguläre Sprachen ist. Es ist aber halt etwas komplizierter.
Die Negation vom Pumping Lemma (womit man beweist, dass eine Sprache nicht regulär ist) lautet:
Für jede konstante k>=0
Gibt es ein Wort w mit |w| >= k
Sodass für jede Zerlegung w = xyz mit |xy|<=k und |y| >=1
Ein i aus N_0 existiert, sodass xy^iz nicht in der Sprache ist.
Du musst also für jede mögliche Konstante ein Wort konstruieren, welches die Negation des Pumping Lemmas erfüllt.
Bei deiner Sprache eignet sich das Wort 0^k1^k.
Versuche Mal die restlichen Schritte selbst durchzuführen (also zu zeigen, dass für jede korrekte Zerlegung es nicht möglich ist, das Wort auf/ oder abzupumpen)
ahso ich darf sowas kreiren? Also ich darf die abgeleitete Sprache L1 erstellen die eine Teilmenge von L ist und das Pumping Lemma muss auch da alle Bedingungen erfüllen?
Zum Beispiel wäre in deinem Beispiel das Pumpen nicht möglich weil sonst die Struktur von der Sprache L1 0^k1^k kaputt gehen würde oder eine Seite zu viele Zeichen hätte.
Also ist es erlaubt von meiner Sprache abgeleitete Sprachen die eine Teilmenge von der ursprünglichen Sprache sind zu erstellen mit ihren eigenen Bedingungen die aber die Bedingung von L erfüllen wie jetzt beispielsweise 0^k1^k? Zum beispiel nehmen wir da das wort 000111 und pumpen 01 dann kommt 0001010111 raus was die Regeln von L erfüllt aber nicht von L1
ahso ich darf sowas kreiren? Also ich darf die abgeleitete Sprache L1 erstellen die eine Teilmenge von L ist und das Pumping Lemma muss auch da alle Bedingungen erfüllen?
Wo habe ich das behauptet?
Ich habe gesagt, dass du das WORT 0^k1^k betrachten sollst, um zu zeigen, dass die Konstante k nicht geht.
Ich glaube mein Fehler war die ganze Zeit das ich davon ausgegangen bin das ich in meinen Wörtern keine Variablen wie z.b. k benutzen darf. Also ist das erlaubt? Ich glaub dann habe ich es auch komplett verstanden.
Du musst das Wort in Abhängigkeit von der pumpingkpmstante wählen, die du widerlegen willst.
Dank dir hab ichs jetzt wieder verstanden. danke du bist der beste 👌
Sorry aber ich versuch seit 6 Stunden das Pumping Lemma zu verstehen aber hab es immernoch nicht raus.
Angenommen wir nehmen die Sprache L:={0,1 | |w|0=|w|1}
also 0 und 1 kommen gleichoft vor. Aber egal was man macht es kommt eine reguläre sprache raus weil es immer ne folge von 01 oder 10 gibt welches man pumpen kann. Weißt du was ich da übersehe?
Aber in meiner Lösung steht das es nicht regulär ist.