| |
| Autor |
 Pumping Lemma kontextfreie Sprache |
|
seonix
Aktiv 
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 
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
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
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
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
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
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
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 
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 
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. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
