Informatiker Board | Theoretische Informatik | Pumping-Lemma kontextfreie Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping-Lemma kontextfreie Sprachen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Pumping-Lemma kontextfreie Sprachen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Nerode
unregistriert

Pumping-Lemma kontextfreie Sprachen

Zitatantwort auf diesen Beitrag erstellen

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?

12.09.2014 11:48

Joejoe
Grünschnabel

Dabei seit: 30.05.2014
Beiträge: 4

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

13.09.2014 14:50

Nehmen Sie Joejoe in Ihre Freundesliste auf

Nerode
unregistriert

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.

14.09.2014 11:36

Joejoe
Grünschnabel

Dabei seit: 30.05.2014
Beiträge: 4

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

14.09.2014 12:08

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping-Lemma kontextfreie Sprachen