Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frühjahr 2004 I-4b) mit Pumping-Lemma
Hi,
Hätte zu dieser Aufgabe eine Frage wie genau löse ich diese Aufgabe mit dem Pumping Lemma?
Steht zwar im Schöning auf Seite 57 aber verstehen tue ich diesen Beweis nicht wirklich…kann mir wer den erklären.
Habe es nun so gelöst…
S->aAbBc
A->aAb
A->leere Menge
B->bBc
B->Leere Menge
daraus folgt das dies eine kontexfreie Sprache ist…
denke mal mit pumping wäre dieses eindeutiger bzw. würde wohl volle Punktzahl geben…aber wie gesagt null plan wie das gehen soll 
die sprache ist ja dann:
a^n b^(n+m-2) c^m
wenn du jetzt sagst das m = 0 ist haste a^n b^(n-2)
das ist zwar nicht ganz a^n b^n, lässt sich aber genauso pumpen.
k ist pumpzahl, dann ist a^k b^k-2
da |v| >= 1 ist und |uv| <= k sein muss kann v nur in a^k sein … naja und dann kannste halt beliebig kaputtpumpen weil du ja nur a’s pumpen kannst und die b’s dabei gleich beiben …
ich glaube das es so richtig ist
Du kannst mit dem Pumping-Lemma nur zeigen, dass die Sprache NICHT regulär ist. Das heißt überhaupt nicht, dass sie kontextfrei ist.
Du kannst auch zeigen, dass sie evtl. NICHT kontextfrei ist (wenn sie z.B. kontextsensitiv oder Typ 0 ist). :finger:
Ich würde die Aufgabe b) (Man beweise: L ist kontextfrei) erledigen, indem ich einen Kellerautomaten angebe, der die Wörter der Sprache akzeptiert.
Zur a) fällt mir grad nicht ein, wo man das P-Lemma ansetzt. Lieber mit Myhill-Nerode, weil a[sup]n[/sup]b[sup]n+m[/sup] unendlich viele Äquivalenzklassen (nämlich m∈N) sind. 
jo ich weiss das ich nur zeigen kann das sie nicht kontextfrei ist aber wenn ich das nicht beweisen kann mit pump dann zeige ich doch damit das sie kontextfrei ist oder?
Nee - du zeigst damit gar nix. Pump-Lemma geht immer nur in eine Richtung. 
Entweder, du kannst das Lemma anwenden um einen Widerspruch zu erzeugen, um die Behauptung “L ist regulär” oder “L ist kontextfrei” zu widerlegen oder du kannst es vergessen.
Schade gehtn das was ich oben geschrieben habe auch?oder fehlt da noch was?
Kellerautomat ist ja ein wenig dumm zu zeichnen oder?
achso ich dachte das sei jetzt die aufgabe wo du nach einnander die chomsky leveln durchmachen musst mit der spache.
aber auch dann …
wenn du kontextfreie produktionen findest und das ganze auch regulär kaputtpumpen kannst, kann sie wohl nur noch kontextfrei sein …
mit pump lemma kannste nur zeigen das die sprache nicht regulär bzw kontextfrei ist und sonst leider nix …
dazu sage ich nur :THI stinkt!!! 
Ich würde schon sagen, dass das geht. Wenn du eine kontextfreie Grammatik angeben kannst (natürlich vollständig formal), ist die Sprache kontextfrei.
Ist nur die Frage, ob man noch zeigen muss, dass die Grammatik genau das tut, was sie soll. Meiner Meinung nach, muss man das nicht extra tun. 
ok dann danke für Eure Antworten evtl. Fragen folgen bis Donnerstag dann
[vergesst es war nicht wichtig]
stopp das geht nicht ganz: du zeigst eventuell dass die sprache kontextfrei ist, indem du eine grammatik angibst, aber du musst dazu leider noch beweisen, dass deine grammatik genau die sprache erzeugt: 1) alle woerter der sprache werden erzeugt. 2) alle erzeugten woerter sind auch wirklich in der sprache.
dann allerdings…
ich hoffe allerdings, dass du damit nicht zeigen willst, dass sie deshalb nicht regulaer sein kann oder sowas…
nö das habe ich in der a schon gezeigt mit pump lemma
kellerautomaten sind, wenn man mal die klausuren durchschaut irgendwie nicht vertreten (vielleicht ein mal oder so), kann das sein?
naja, ich habe mir sagen lassen, dass kellerautomaten gross durchzunehmen eh keinen grossen sinn haette, da sie praktisch unrealisierbar seien (!)
?? nicht deterministisch koennen die teilweise sehr ekelig werden weil jede „moeglichkeit“ n eigenen keller hat … aber deterministisch isses doch einfach nur ein automat mit nem (keller|stack) … also wenn du touring kannst, kannst auch keller, da ersteres das letzte simulieren kann …