Kann einer das Pumping-Lemma für Idioten erklären?
Checke irgendwie nicht, wie ich überprüfen soll, mit dem pumping-Lemma, ob eine Sprache regulär ist oder nicht.
2 Antworten
Reguläre Sprachen: Wenn Du z.B. x verschiedene Zustände hast, dann kann man maximal x-1 mal die Zustände wechseln. Wechselt man x mal die Zustände, hat man mindestens einen Zustand doppelt erreicht. Wenn man aber einen Zustand doppelt erreichen kann, muss es notwendig eine Schleife geben.
Daraus ergibt sich: Wenn wir ein Wort haben, welches mehr Buchstaben hat als es Zustände gibt (oder gleich viel), dann muss mindestens einmal eine Schleife durchlaufen sein. Wenn aber die Schleife einmal durchlaufen worden ist, kann ich auch ein Wort bilden, in welchem man die Schleife zweimal oder dreimal oder kein mal oder tausend mal etc. durchläuft.
Daraus ergibt sich: Wenn man ein Wort wählt, welches hinreichend lang ist, dass muss dieses Wort irgendwo eine Stelle haben, in welchem es in die Schleife eintritt und wo es wieder heraustritt. Diesen Stellen kann man also aufpumpen (Schleifenanzahl erhöhen) oder herauspumpen (kein Schleifendurchlauf). Das geht bei allen langen Wörtern der regulären Sprache.
Ist die Sprache aber nicht regulär, kann man sehr lange Wörter bilden, in welchen man keine pumpbare Stelle findet, da die Wörter in der (nicht regulären Maschine) ohne Schleifen gebildet werden, man kann also keine Eintrittsstelle in eine Schleife finden, wo man weiterpumpen könnte.
Z.B. a hoch l mal b hoch l. Diese Sprache ist nichr regulär (da sich ein DEA keine beliebige Anzahl merken kann), folglich findest Du keine Aufteilung in dem Wort a hoch k mal b hoch k mit sehr hohem k, wo man einfach mal an einer (!) Stelle das k erhöhen könnte und das Wort immer noch in der Sprache bleibt --> diese Sprache ist nicht mit einer Schleife in einem DEA darstellbar --> keine Pumplogik anwendbar. (mit zwei Pumpstellen ginge es, siehe unten bei kontextfreien Sprachen).
Pumpen in kontextfreien Sprachen: Im Prinzip wie bei regulären Sprachen, außer dass die Schleife nicht in den Zuständen ist, sondern in der Grammatik: Man muss mindestens eine der Grammatikregeln zweimal anwenden, wenn das Wort sehr lange ist. Kann man aber eine Grammatikregel zweimal anwenden, könnte man sie logischerweise auch 3mal, 10mal, 100mal oder auch kein Mal (da sie mit einer Variable fortsetzt, kann also keine finalisierende Regel sein). Da die Grammatikregel jedoch an zwei Stellen valide werden kann, gibt es logischerweise zwei Pumpstellen und die Überlänge bezieht sich dann auf Pumpstelle zu Pumpstelle. An diesen zwei synchronen Pumpstellen sieht man auch schön den Zusammenhang zur Grammatik bzw. zum Kellerautomaten, welche beide es ermöglichen, quasi eine Zahl zu merken.
So klarer?
hauptsache, eine 2 kommt vor, nicht eine 1.
Die Sprache ist offensichtlich regulär, richtig, der DEA hat zwei Zustände. Der Übergang vom Start zum finalen akzeptierenden Zustand ist die 2.
NEIN
Für die positive Bestätigung, dass es pumpbar ist, genügt, dass eine Pumpstelle existiert, nicht erforderlich ist, dass überall gepumpt werden kann. Existenzquantor, nicht Allquantor - erst bei der Verneinung wird der Existenzquantor ein negativer Allquantor: für alle Stellen gilt, dass nicht pumpbar.
Wir haben im DEA zwei Schleifen, nämlich am Startzustand auf sich selbst und am akzeptierenden Zustand auf sich selbst. Da kann ich pumpen was das Zeug hält. Also in Deinem Beispiel kann man nur bei der Null pumpen bzw. bei der 1 oder der 0 danach, aber nicht bei der 2 (quasi dort wo das Sternchen ist - nicht dort, wo weder Stern noch Plus ist).
ACHSO! Ich muss nur eine aufpumpbare Stelle finden O.o
Ja, genau. Ich gebe Dir noch ein Beispiel: (01)*
Auch regulär, einfach zwei Zustände, Start ist der akzeptierende Zustand, dann gibt es noch einen Zustand Z, von dem kommt man vom Start mit einer 0 und von diesem Zustand Z kommt man zurück mit einer 1.
Wo ist hier die Pumpstelle? Bevor weiterlesen, vielleicht selbst zu lösen versuchen.
Die Pumpstelle ist komplett (01), ist also Minimum 2 Zeichen lang. Wenn man xyz als Aufteilung nimmt, dann sind x = z = leeres Wort und y = (01). Damit habe ich eine pumpbare Zerlegung für die Mindestgröße 2 gefunden und damit ist die Sprache pumpbar.
Weiteres Beispiel 01(10011)*00. Hier ist die Mindestlänge 5 und der Pumpteil ist y = (10011), x ist 01 und z = 00.
Bei 0(1)*0(11)*0(1)* hast Du sogar drei mögliche Pumpstellen, zwei mit der Größe 1 und eine mit der Größe 2.
Aber Moment, warum kann ich den mit dem Pumpinglemmar nicht zeigen, dass eine Sprache regulär ist? Dadurch, dass ich zeige, dass die Sprache nicht regülär ist, ist die ja regulär?
Wir haben das immer anhand einer Konversation erklärt. Dazu Person A und Person B.
A: Hier hast du eine Sprache L.
B: Ist L regulär? Ich arbeite nur mit regulären Sprachen.
A: Nehmen wir mal an, L ist regulär.
B: L hat eine Pumplänge, genannt p.
A: Danke, dann gebe ich dir jetzt den String s aus L den ich in Abhängigkeit von deinem p gebildet habe, sodass |s| >= p.
B: Danke. Ich zerlege diesen String jetzt in die drei Teile x,y und z. Ich sage aber nicht, was die Teile sind. Nur: |y| > 0 und |xy| <= p. y darf so oft herausgenommen oder hintereinander eingefügt werden wie du willst. Der dadurch entstehende String wird immer noch aus L sein.
A: Ich habe deine Vorgaben erfüllt. Aber wenn ich y n-mal kopiere oder lösche ist der neue String nicht in L weil ....
B: Dann war L wohl doch keine reguläre Sprache. Deine Annahme war falsch.
Der letzte Satz von A ist das wichtigste. Du versuchst also einfach ein Gegenbeispiel zu finden. Findest du das nicht, ist die Sprache vermutlich regulär.
Danke, aber mal ein einfaches Beispiel;
L={ (0+1)* 2 (0+1)* }
Also ich habe jetzt eine Sprache die aus beliebig vielen 0´ en udn 1 bestehen kann, hauptsache eine 1 kommt vor.
Die sprache ist offensichtlich regulär.
Wenn ich nun sage, ich wende das Pumpinlemma an.
Ich habe z. B. 002110
ich kann ja jetzt sagen ich erhöhe die 2, nach Pumpinglemma und meine neue Menge sollte noch zur Sprache gehören:
002222110, jetzt wäre das aber nicht mehr in L? Obwohl ja L regulär ist...
Wenn du das Pumping Lemma korrekt angewendet hast, dann ist die Sprache nicht regulär.
Du kannst mit dem Pumping Lemma nicht herausfinden ob eine Sprache regulär ist, sondern nur, dass sie nicht regulär ist.
Herausfinden ob es regulär ist, geht z.B. mit einem DEA.
Ja ich mein, ich will ja herausfinden, dass die nicht regulär ist, aber das darf ja eigentlich nicht sein? Weil die ist ja offensichtlich regulär
Okay danke, aber warum kann ich nicht sagen, dass etwas regulär ist durch das Pumpinglemmar? Wenn ich bei etwas zeige, dass es mit dem Pumpinglemmar nicht nicht regulär ist, so kann es ja nur noch regulär sein oder O || O?
Danke, aber mal ein einfaches Beispiel;
L={ (0+1)* 2 (0+1)* }
Also ich habe jetzt eine Sprache die aus beliebig vielen 0´ en udn 1 bestehen kann, hauptsache eine 1 kommt vor.
Die sprache ist offensichtlich regulär.
Wenn ich nun sage, ich wende das Pumpinlemma an.
Ich habe z. B. 002110
ich kann ja jetzt sagen ich erhöhe die 2, nach Pumpinglemma und meine neue Menge sollte noch zur Sprache gehören:
002222110, jetzt wäre das aber nicht mehr in L? Obwohl ja L regulär ist..