Dispo(sitionskredit) für Kellerspeicher ?
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.
Altklausuren ThInf - Pumping Lemmata.
Mit “I-4” überschriebene Sprache L = {a [sup] n [/sup] b [sup] n+m [/sup] c[sup] m [/sup] | n,m > 0 }
zu beweisen war: a) L ist nicht regulär b) L ist kontextfrei.
Zur Diskussion:
a) ließ sich dadurch beweisen, dass L reg. P.E. nicht hat.
b) es lässt sich zwar zeigen, sowohl, dass L die kf. P.E. nicht nicht hat also besitzt, aber kontextfrei ist L damit doch noch lange nicht… Oder?
Ist es ein Beweis zu sagen, dass Sprache nicht kf., weil beim Einlesen von b’s Teller vom Stapel genommen werden müssen und der Kellerspeicher leider keinen doppelten Boden hat, bei dem man “Minus”-Teller anhäufen kann. (kellerspeicher hat kein Tellerdispo)
Was meint Ihr?
Bei jedem a (n viele) legst du ein a auf den Stapel. Dann kannst du mit den ersten n bs den Stapel leer-räumen. Wenn du aufs Grundsymbol stößt, wechselst du den Zustand und legst bei jedem zusätzlichen b (m viele) ein b auf den Stapel. Irgenwdann wechselst du nochmal den Status, akzeptierst nur noch cs und räumst den Stapel wieder leer.
Sehr gut. Diesen push down automaton habe ich gesucht.
danke 
L ist kontextfrei => L besistzt kontextfreie Pumpeigenschaft (was ich auch zeigen konnte!)
Aus der Tatsache dass du zeigen konntest, dass L die kf. PE besitzt folgt noch lange nicht, dass L ebenfalls kontextfrei ist.
Unsre Vorlesungsmitschrift zu dem Thema:
Diese zwei Aussagen schliessen daher nicht aus, dass eine Sprache, die nicht kontextfrei ist, die kontextfreie PE hat.
Durch die Angabe eines (korrekten) NDPAs fuer L, wie L.F.Ant das hier skizziert hat, kannst du folgern dass L kontextfrei ist.
-chris
so ist es. widerspreche dir nicht.
würdest du dir die aufgabenstellung (siehe Strehl Seite) aber mal anschauen, würdest du bemerken, dass genau danach gefragt war, nämlich die, ob die sprache kontextfrei ist. die frage lautete nicht, ob das k.f. P.E erfüllt ist.
aber du hast natürlich recht. einfacher wäre es durch angabe einer grammatik mit w_1 ∈ V zu zeigen, dass diese sprache kontextfrei ist…
QUIZFRAGE, Wie sieht diese Grammatik aus…
∑ = {a,b,c},
gesucht P, V.
Wie hast du denn gezeigt, dass L kontextfrei ist ?
Ich hab
so interpretiert, dass du gezeigt hast, dass L die kf. PE besitzt und daraus folgern willst, dass L kf. ist. Daher auch meine Erklaerung.
S → aAbbCc
A–> aAb|Epsilon
C–>bCc| Epsilon
V={S,A,C}
bis zu deinem Post, hatte ich nicht gezeigt, dass L kontextfrei ist, deshalb habe ich ja den Thread erstellt.
Ich konnte zeigen, dass k.f. P.E. erfüllt ist, daraus folgt aber -wie du treffend festgestellt hast- eben nicht, dass die Sprache auch kf ist.
Daher mein Thread. Ich sinnierte darüber nach, ob die Sprache k.f. sein könne bzw. wie ein solcher PDA ausssehen müsse… Lies dir meinen allerersten Beitrag genau durch, dann weisst du was bei mir im hirn vorgegangen ist…
Die Lösung habe ich auch, wenn du Groß C durch Groß B substitutierst. Aber deine Bezeichnungen sind natürlich hübscher.