Pumping-Lemma kontextfreie Sprachen

Neue Frage »

Auf diesen Beitrag antworten »
Nerode Pumping-Lemma kontextfreie Sprachen

Meine Frage:
Hallo,

bei dieser Beispielsprache möchte ich zeigen, dass sie nicht kontextfrei ist: [latex] L=\left\{ a^{2^n}|n\in\mathbb{N}\right\}[/latex]

Meine Ideen:
Ich verwende das Pumping-Lemma: Sei also [latex]n\in\mathbb{N}[/latex] fest. Offenbar ist mit [latex]z=a^{2^n}[/latex] auch [latex]z\in L[/latex] und [latex]|z|=2^n\geq n[/latex].
Zu jeder Zerlegung [latex]z=uvwxy[/latex] wähle ich nun [latex]i=2[/latex], dann gilt: [latex]2^n < |uv^iwx^iy| = |uv^2wx^2y|=|uvwxy|-|v|-|x|+|v^2x^2|\\=2^n-|v|+|v^2|-|x|+|x^2| = 2^n+|vx|\leq 2^n+n < 2^{n+1}[/latex]
und somit muss [latex]uv^2wx^2y \notin L[/latex] gelten.

Darf man das so machen?
 
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
Auf diesen Beitrag antworten »
Nerode

Ja das der Schritt unnötig war ist mir nach dem Posten des Beitrags auch aufgefallen.
Zitat:
Uebrigens, das Pumping Lemma fuer kontextfreie Sprachen ueber einelementigen Alphabeten wie diesem hier entspricht dem Pumping-Lemma fuer regulaere Sprachen.

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.
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
 
 
Neue Frage »
Antworten »


Verwandte Themen

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