Informatiker Board | Druckvorschau: Pumping-Lemma kontextfreie Sprachen

Geschrieben von Nerode am 12.09.2014 um 11:48:

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?

Geschrieben von Joejoe am 13.09.2014 um 14:50:

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

Geschrieben von Nerode am 14.09.2014 um 11:36:

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.

Geschrieben von Joejoe am 14.09.2014 um 12:08:

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