Pumping Lemma für reguläre Sprachen

Neue Frage »

eb47vebe Auf diesen Beitrag antworten »
Pumping Lemma für reguläre Sprachen
Hallo,

wann immer ich versuche das Pumping Lemma anzuwenden oder im Internet nach Informationen über die Funktionsweise suche bleiben einige Fragen offen.

1. Bei sämtlichen Erklärungen die ich fand, kam die Zerlegung in uvw immer förmlich aus dem Himmel, gibt es da einen Trick oder eine Vorschrift wie sich dass am einfachsten finden lässt?

2. Ist diese Zerlegung immer eindeutig? Kann mir dass kaum vorstellen, aber ist es möglich dass es mit dem Pumping Lemma für dieselbe reguläre Sprache verschiedene Zerlegungen gibt?

Es will mir einfach nicht in die Birne dieses verfluchte Lemma ;-)

Vielen Dank für Eure Hilfe im Voraus

eb..
chrizke Auf diesen Beitrag antworten »

Nein die Zerlegung ist nicht eindeutig. Es existiert lediglich mindestens eine, sofern die Sprache regulär ist.

Aber das eigentlich interessante an diesem Lemma ist ja, dass du damit zeigen kannst, dass eine Sprache nicht regulär ist. Und dafür testest du alle möglichen Zerlegungen, was für die Sprachen, die man so als Übung bekommt, oft sehr überschaubar ist und selten 5 Fälle übersteigt.

Also angenommen, die Sprache sei regulär. Dann findet man eine Zerlegung eines Wortes w, sodass w = xyz.
Die Bedingung, dass das Wort länger als ein p sein muss, ignorieren wir erstmal. Wichtig ist erstmal nur, dass y nicht das leere Wort sein darf.

Das spannende ist nämlich das Pumpen. Jetzt besagt das Lemma nämlich, dass wenn man solch eine Zerlegung hat für eine reguläre Sprache, dann kann man das y "aufblähen" und zwar muss gelten:



Also egal wie oft man in der Mitte des Wortes das y einfügt, es muss immernoch in dieser Sprache L sein.

Und hier setzt man an, wenn man zeigen will, dass eine Sprache nicht regulär ist. Wenn du nämlich zeigst, dass für alle Zerlegungen xyz dieses Aufblähen (Pumpen) nicht funktioniert, ist es keine reguläre Sprache.
Beispiel dazu gibts morgen früh, ich geh jetzt erstmal schlafen Schläfer
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »