Logik/reguläre Sprachen: Pumping Lemma

Neue Frage »

bandchef Auf diesen Beitrag antworten »
Logik/reguläre Sprachen: Pumping Lemma
Aufgabe:
Beweisen oder widerlegen sie mit dem Pumping-Lemma, dass die folgende Sprache regulär ist:







Hi Leute!

Ich hab mit dem Pumping-Lemma so meine Probleme. Ich hoffe ihr könnt mir an dieser Stelle weiterhelfen! Ich hab dann mal so angefangen:


Wir treffen am Anfang eine Annahme: L ist regulär.

Sei die Konstante des PL, dann gilt: mit .

mit , , und


Ab dieser Stelle hab ich nun meine Probleme. Jetzt muss ich eine Zerlegung in uvw angeben. Aber genau das verstehe ich immer nicht. Könnt ihr mir ab hier weiterhelfen?
kiste Auf diesen Beitrag antworten »
RE: Logik/reguläre Sprachen: Pumping Lemma
Zitat:
Original von bandchef
Ab dieser Stelle hab ich nun meine Probleme. Jetzt muss ich eine Zerlegung in uvw angeben. Aber genau das verstehe ich immer nicht. Könnt ihr mir ab hier weiterhelfen?

Nein du musst zeigen: Für jede Zerlegung gibt es ein i so dass uv^iw die Länge einer Primzahl hat.

Die Sprache ist sicherlich nicht regulär, ad hoc sehe ich aber die Konstruktion nicht mit der wir die Primzahl bekommen. Ein guter Start ist es vllt. das Wort z obda mit ungerader Länge zu nehmen.

Einfacher ist es jedoch das Komplement von L zu betrachten und darauf das PL anzuwenden.
 
 
bandchef Auf diesen Beitrag antworten »

Hm, vielleicht es dann einfacher, wenn ich andere Sprache als Beispiel angebe:



Wir treffen am Anfang eine Annahme: L ist regulär.

Sei die Konstante des PL, dann gilt: mit .

, ,

Jede gültige Zerlegung hat die Form:


Hier hab ich nun wieder meine Probleme...


Edit: Einfacher ist es jedoch das Komplement von L zu betrachten und darauf das PL anzuwenden. Diesen Satz verstehe ich nicht ganz. Das Komplement von L enthält ja alle Wörter der Sprache L die nicht in L enthalten sind, oder? Ich hab immer gedacht, dass die "Annahme" am Anfang des Beweises widerlegt werden muss. Da ich eben annehme, dass die Sprache regulär ist, reicht es zu zeigen, dass sie es eben nicht ist.

Dass ich eine Zerlegung für uv^iw finden muss ist klar; dass war grad nur ein Tipfehler... Dennoch hab ich das Problem, dass ich eine Zerlegung angeben muss, die für ein zeigt, dass die Sprache nicht regulär ist.
kiste Auf diesen Beitrag antworten »

Bei deinem Quadratbeispiel hilft doch schon i=2.

Das mit dem Komplement gilt weil . Deswegen kann man auch zeigen dass das Komplement von L nicht regulär ist.
bandchef Auf diesen Beitrag antworten »

Ich hab jetzt das hier auf meinem Blatt stehen:




Annahme: L ist regulär.

Sei die Konstante des Pl, dann gilt: .

mit

Sei z = uvw eine Zerlegung von z mit .



Wie sieht diese Zerlegung nun aus? Das ist immer das Problem, dass ich beim PL hab...
kiste Auf diesen Beitrag antworten »

Zitat:
Original von bandchef
Wie sieht diese Zerlegung nun aus? Das ist immer das Problem, dass ich beim PL hab...

Weiß man nicht, musst halt einen Widerspruch finden egal wie die Zerlegung aussieht.
Neue Frage »
Antworten »



Verwandte Themen

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