Pumping-Lemma kontextfreie Sprachen |
12.09.2014, 11:48 | Auf diesen Beitrag antworten » | ||
Nerode | Pumping-Lemma kontextfreie Sprachen Meine Frage: Hallo, bei dieser Beispielsprache möchte ich zeigen, dass sie nicht kontextfrei ist: Meine Ideen: Ich verwende das Pumping-Lemma: Sei also fest. Offenbar ist mit auch und . Zu jeder Zerlegung wähle ich nun , dann gilt: und somit muss gelten. Darf man das so machen? |
||
|
|||
13.09.2014, 14:50 | Auf diesen Beitrag antworten » | ||
Joejoe | RE: Pumping-Lemma kontextfreie Sprachen Hallo Nerode, deine Abschaetzung ist vollkommen richtig. Ein paar Dinge: der Schritt |uvwxy|-|v|-|x|+|v^2x^2| ist unnoetig kompliziert und kann zu |uvwxy|+|vx| zusammengefasst werden. Uebrigens, das Pumping Lemma fuer kontextfreie Sprachen ueber einelementigen Alphabeten wie diesem hier entspricht dem Pumping-Lemma fuer regulaere Sprachen. Liebe Gruesse |
||
14.09.2014, 11:36 | Auf diesen Beitrag antworten » | ||
Nerode | Ja das der Schritt unnötig war ist mir nach dem Posten des Beitrags auch aufgefallen.
Das müsste der Satz von unitären kontextfreien Sprachen sein, oder? Reicht es dann auch zu zeigen, dass die Sprache nicht regulär ist? Dann könnte man ja hier auch die Myhill-Nerode Äquivalenzrelation nutzen. |
||
14.09.2014, 12:08 | Auf diesen Beitrag antworten » | ||
Joejoe | Hier reicht es das Pumping-Lemma fuer regulaere Sprachen zu verwenden. Um mit dem Satz von Myhill-Nerode zu beweisen, dass diese Sprache nicht regulaer ist, musst du zeigen, dass die Aequivalenzklassen [a^2^n] und [a^2^m] mit m != n nicht aqeuivalent sind. Es gibt also unendlich viele Aequivalenzklassen. LG |
||
Anzeige | |||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|