Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Pumping Lemma kontextfreie Sprache
Autor
Universität/Hochschule Pumping Lemma kontextfreie Sprache
seonix
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.04.2022
Mitteilungen: 38
  Themenstart: 2022-06-17

Hallo, Zeigen oder Widerlegen Sie: Für jede kontextfreie Sprache \( L \) gilt, dass \( L^{+}:=\left\{w^{n} \mid w \in L, n \geq 1\right\} \) kontextfrei ist. wähle w = abb ich habe nicht wirklich viel Erfahrung mit dem Pumping Lemma, aber wenn ich das einigermaßen richtig verstanden habe, dann kann man z.B. ein Wort z = abbabb(also w^2) wählen und es dann in uv^{i}wx^{i}y zerstückeln. Dann könnte man ja vwx = bb wählen mit p, q aus N und p = 2 und q = 2, woraus das Wort abbbbabb entstünde was allerdings nicht in der Sprache liegt. Daraus folgere ich, dass die Sprache nicht kontextfrei ist. Ist das so im Groben richtig ? Wenn nein, kann mir jemand erklären wie man in diesem Fall das Pumping Lemma richtig benutzt. mfg seonix


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3232
  Beitrag No.1, eingetragen 2022-06-17

Dein Vorgehen ist zumindest schwer nachvollziehbar, vermutlich auch falsch. Mein erster Impuls wäre, eine Grammatik anzugeben. 1. Betrachte in CNF alle Produktionen der Sprache L mit Form \(S \to AB\) 2. Ergänze diese um: \(S \to CC\) \(C \to CC\) \(C \to AB\) 3. Streiche ggf. die Produktion der Form \(S \to \epsilon\) Falls das funktioniert, wäre bewiesen, dass die Sprache $L^+$ kontextfrei ist. Edit: Funktioniert leider nicht.


   Profil
seonix
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.04.2022
Mitteilungen: 38
  Beitrag No.2, vom Themenstarter, eingetragen 2022-06-17

Hallo, also ich habe jetzt grade gesehen, dass man die Aufgabe auch eher nicht mit dem Pumping Lemma lösen sollte, aber mir fällt nun wirklich kein Weg ein wie man das beweisen bzw. widerlegen kann. Edit: Ich habe jetzt doch gesehen, dass man überprüfen muss, ob die Sprache abgeschlossen ist gegen: Vereinigung Konkatenation Sternbildung Homomorphismen Durchschnitt regulärer Mengen


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1297
Wohnort: Kiel, Deutschland
  Beitrag No.3, eingetragen 2022-06-17

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Ich würde da noch naiver rangehen. Da \(L\) kontextfrei ist, gibt es eine CFG, die genau \(L\) erzeugt. Sei \(G\) eine solche. Entferne aus ihren Produktionen alle Regeln, mittels derer sich das leere Wort ableiten lässt. Gehe hierbei so sparsam wie möglich vor. Also salopp gesprochen: Streiche alle \(\varepsilon\) aus rechten Regelseiten. Nichtterminalsymbole, die danach ins Leere zeigen, fliegen komplett raus. Die entstehende Grammatik ist kontextfrei, da die linken Regelseiten nicht verändert, höchstens entfernt, werden. Also gilt die Behauptung: Zu jeder kontextfreien Sprache \(L\) ist \(L^+\) kontextfrei. mfg thureduehrsen\(\endgroup\)


   Profil
seonix
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.04.2022
Mitteilungen: 38
  Beitrag No.4, vom Themenstarter, eingetragen 2022-06-17

Hallo, also soll ich für jede kontextfreie Sprache L G= (V, T\{Epsilon}, P\{Epsilon}, S) definieren, ich bin mir ziemlich unsicher wie ich das formal aufschreiben soll.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3232
  Beitrag No.5, eingetragen 2022-06-17

\quoteon(2022-06-17 16:38 - thureduehrsen in Beitrag No. 3) Die entstehende Grammatik ist kontextfrei, da die linken Regelseiten nicht verändert, höchstens entfernt, werden. \quoteoff Die entstehende Grammatik erzeugt jedoch nicht die geforderte Sprache \[L^+ = \{w^n | w \in L, n \geq 1\}\], also die Sprache der Vielfachen der Wörter der Sprache. Meine Grammatik oben erzeugt $L^+$ in der übliche Bedeutung als nichtleere Konkatenation beliebiger Wörter aus $L$. Das passt leider auch nicht. Ich hatte mich da von der merkwürdigen Notation irritieren lassen. Mich wundert mittlerweile die Aussage, dass das Pumpinglemma nicht helfen soll. Man sollte für kontextfreie Klassiker wie $L=\{a^nb^n\}$ doch mit vertretbarem Aufwand nachweisen können, dass die zugehörigen Vielfachen dieses nicht erfüllen. Ich würde das konkret mal versuchen.


   Profil
seonix
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.04.2022
Mitteilungen: 38
  Beitrag No.6, vom Themenstarter, eingetragen 2022-06-17

Hallo, also ich hab mich zu ungenau ausgedrückt, tut mir leid, ich habe das Wort abb selber gewählt, also es stand davon nichts in der Aufgabe. In der Aufgabe steht folgendes: https://matheplanet.com/matheplanet/nuke/html/uploads/b/55507_fbceeed1c8052d9c20aa76210c240d49.png Man soll hier glaube ich das anhand der Abschlusseigenschaften kontextfreier Sprachen machen. Also diese für L zeigen, und dann folgern. L ist kontextfrei => L^+ ist kontextfrei. Aber ich bin mir unsicher, vor allem wüsste ich auch nicht genau wie ich das formal zeigen soll.


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1297
Wohnort: Kiel, Deutschland
  Beitrag No.7, eingetragen 2022-06-17

\quoteon(2022-06-17 18:49 - DerEinfaeltige in Beitrag No. 5) Ich hatte mich da von der merkwürdigen Notation irritieren lassen. \quoteoff Da sind wir schon zwei 😎 Ich setze mich morgen Nachmittag auch mal ran. mfg thureduehrsen


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3232
  Beitrag No.8, eingetragen 2022-06-18

Beweisskizze mit Pumpinglemma: Die Sprache $L=\{a^nb^n\}$ ist bekanntlich kontextfrei. Wir widerlegen, dass $L^+ = \{(a^nb^n)^m|m\geq1,n\geq1\}$ kontextfrei ist. Die Pumpingzahl sei $p$. Wähle $z=(a^pb^p)^2$: Der Mittelteil $vwx$ jeder gültigen Zerlegung hat die Form $a^mb^n,m+n\leq p$ oder $b^ma^n,m+n\leq p$. Im ersten Fall kann man den betrachteten Abschnitt durch pumpen von $a^i$ und $b^i$ zwar innerhalb von $L$ halten, erhält dabei jedoch ein Wort der Form $z' = a^mb^ma^nb^n,m\neq n$, welche nicht in der Sprache $L^+$ gemäß der Definition aus der Aufgabenstellung liegt. (Wohl aber innerhalb der tatsächlich kontextfreien Sprache $L^+$ gemäß üblicher Definition!) Im zweiten Fall zerstört jedes Pumpen bereits die ursprüngliche Form aus $L$.


   Profil
seonix
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.04.2022
Mitteilungen: 38
  Beitrag No.9, vom Themenstarter, eingetragen 2022-06-18

Hallo, ja ich glaub jetzt auch, dass das eher mit dem pumping lemma gelöst werden soll, ich habe die aufgabenstellung falsch verstanden, ich dachte man müsse jetzt z.B. zeigen, dass die Sprache unter Iteration usw. abgeschlossen ist. Dieses "Abschlusseigenschaften kontextfreier Sprachen" hat mich verwirrt. Edit: Kann es dann vielleicht sein, dass wir dann mit dem Pumping Lemma zusätzlich gezeigt haben, dass die Sprache nicht unter Iteration abgeschlossen ist, also, da z.B. (a^nb^n)^m, was ja prinzipiell eine Iteration ist, nicht kontextfrei ist? mfg seonix


   Profil
seonix hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]