Informatiker Board | Theoretische Informatik | Pumping-Lemma kontextfreie Sprachen

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge

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

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.

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

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?