F2-Skript, Theorem 5.17:

Foldende Aussagen sind aequivalent:
1. L \in CF
2. L = L(A) fuer einen beliebigen PDA A
3. L = L(A) fuer einen fast-buchstabierenden PDA A
4. L = L(A) fuer einen buchstabierenden PDA A
5. L = N(A) fuer einen fast-buchstabierenden PDA A

1->2 gilt wegen 5.12, 2->3 wegen 5.11, 4->1 wegen 5.14, aber wie kommt man von 2 nach 3?
1->5 gilt ebenfalls wegen 5.12, alternativ 2->5 wegen 5.13, aber wie kommt man von 5 wieder zurueck nach 1 oder 2?

5.11:

Zu jedem PDA A kann effektiv ein aequivalenter fast-buchstabierender PDA B konstruiert werden

5.12:

Zu jeder kontextfreien Grammatik G kann effektiv ein Kellerautomat A_G konstruiert werden, fuer den N(A_G) = L(A_G) = L(G) gilt.

5.13:

Zu jedem mit Endzustand akzeptierenden PDA A kann effektiv ein PDA B mit L(A) = N(B) konstruiert werden

5.14:

Fuer jeden PDA A ist L(A) eine kontextfreie Sprache

achja, wie verhalten sich in dem Zusammenhang beliebige PDAs, wenn man sie mit leerem Keller akzeptieren laesst? Bisher hatte ich den Eindruck, dass man dann auch nur kontextfreie Sprachen erhaelt, aber die Tatsache, dass die hier nicht mit aufgefuehrt sind, laesst mich irgendwie daran zweifeln… oder wollte Herr Jantzen uns den Beweis nur nicht zumuten?

2->3 wegen 5.11, .., aber wie kommt man von 2 nach 3?

?

tja wie ich das so auf die schnelle ansehe,
fehlt zum endgültigen glück noch ein theorem:
(ich zweifle noch daran, ob es fehlt,
da ich ja so ein großer fan des skriptes bin ;) )

Theorem 5.13 b:
Zu jedem mit leeren Keller akzeptierenden PDA A
kann effektiv ein PDA B mit N(A) = L(B) konstruiert werden.

Beweis:
?, geht hoffentlich

1 <=> 2 gilt wegen 5.14 und 5.12 (ein bischen stoerend ist das "beliebig" in 2, besser waere [finde ich] "fuer einen PDA A", denn wenn man eine Sprache hat ist es ja nicht beliebig welchen PDA man konstruiert um sie zu akzeptieren)

2 => 3 wegen 5.11

3 => 4 kann man entsprechend der Konstruktion des PDA C im Beweis des Theorems 5.14 machen. Dort ging es zwar darum aus PDA B (fast-buchstabierend) einen PDA C (buchstabierend) zu machen mit N(B) = N(C). Dies geht aber entsprechend. [Dabei muesste wichtig sein, dass B wie in Lemma 5.13 konstruiert ist, also insb. $ auf dem Keller verbleibt - bis dieser wirklich geleert werden soll. D.h. um 3 => 4 zu zeigen muss man ggf. ein neues Kellerbodensymbol "vorschieben" (siehe Lemma 5.13) und kann dann wie in Theorem 5.14 verfahren.]

4 => 5 mit Lemma 5.13 (Man beachte den letzten Satz im Beweis. B ist also fast-buchstabierend sofern dies A ist. Da in 4 A buchstabierend ist, ist er auch fast buchstabierend.)

5 => 1 Theorem 5.20 (L = N(A) ist aus detCf (und praefixfrei) und detCf ist natuerlich Teilmenge von Cf (sogar echte, siehe Theorem 5.25))

Ups, entschuldigung. 5 => 1 kann man so nicht stehen lassen. So wuerde es fuer DPDAs sein, aber wir sprechen hier ja von PDAs. Nun, dann eben doch Slater's Theorem 5.13b beweisen [img]http://www.fb18.de/gfx/17.gif[/img]

Für 5 => 1 haben wir also einen fast-buchstabierenden PDA A mit L = N(A). Wir wollen zeigen, dass ein PDA B existiert mit L = L(B).

Allgemeiner: Zu jedem PDA A exisitert ein PDA B mit N(A) = L(B). (Also ohne das fast-buchstabierend.)

Beweiss(idee): B schreibt zuerst ein neues unteres Symbol $ in den Keller und arbeitet dann wie A. Trifft B wieder auf $, dann heisst das, das A seinen Keller geleert hat und das heisst, dass B in seinen Endzustand uebergeht.

Also: Zu den Zustaenden zwei neue dazu (einer davon ist der neue und einzige Endzustand, der andere der neue Startzustand).

Alphabet bleibt. Kelleralphabet erhaelt ein neues Kellerbodensymbol dazu.

In die Kantenmenge kommt eine Kante vom neuen Startzustand zum alten Startzustand hinzu (liest vom Eingabeband das leere Wort, liest vom Stack das neue Kellerbodensymbol, schreibt das neue und das alte (in dieser Reihenfolge, das neue also wieder ganz unten)) und dann von jedem Zustand (des alten Automaten) eine Kante zum neuen Endzustand die dann 'benutzt' wird, wenn nur noch das neue Kellerbodenzeichen im Keller ist. Von der Eingabe wird nichts gelesen. Auf den Keller wird das leere Wort geschrieben.

Fertig. Formaler mit Mengendefinition etc. huebscher, aber ich krieg das hier mit den Zeichen nicht hin (oder kann man hier .tex-Symbolik benutzen?), aber obiges hilft vielleicht schon.

Damit ist auch 5 => 1 gezeigt (eigentlich 5 => 2, aber es galt ja schon 1 <=> 2) und damit ist das alles aequivalent.

Cheers,
Frank

P.S. Noch 7 Tage… bibber [img]http://www.fb18.de/gfx/28.gif[/img]

/edit
veraltet



anmerkung:
zumindest ist nach diesem verfahren N(A) teilmenge von L(B),
aber das reicht ja aus,

zwischen entfernen des alten kellerbodensymbols und
übergang zum endzustand mit neuen kellerbodensymbol
kann man ja noch ne menge anderer dinge machen

Nach dem Verfahren ist N(A) = L(B). Teilmenge wuerde nicht ausreichen, da ja folgender Satz gezeigt werden sollte:

Zu jedem PDA A exisitert ein PDA B mit N(A) = L(B).

Die Aussage, dass man dazwischen noch andere Sachen machen kann verstehe ich nicht ganz. Also ich verstehe sie schon, aber ich verstehe nicht, was du mir damit Sagen moechtest [img]http://www.fb18.de/gfx/22.gif[/img]

Wenn man bspw. einen Produktautomaten konstruiert (den Beweis meine ich), denn sagt man doch auch nicht, dass man da ja jetzt noch beliebig viel ranhaengen kann und deswegen gilt eigentlich nur eine Teilmengen-Beziehung ??

Oder meintest du dies: Wenn L1 die Sprachen sind, die von einem PDA mit Endzustand akzeptiert werden koennen und L2 die Sprachen, die von einem PDA mit leerem Keller akzeptiert werden koennen, so wurde durch obiges nur gezeigt, dass L2 Teilmenge von L1 ist?
Das stimmt. Man kann aber auch zeigen:

Zu jedem PDA A exisitert ein PDA B mit L(A) = N(B).

Damit ist L1 = L2.
Anders ausgedrueckt: Die beiden verschiedenen Moeglichkeiten des Akzeptierens fuehren zu gleichmaechtigen Sprachen.

Sorry, war von mir – das mit dem Login/Logout kriege ich irgendwann auch noch hin [img]http://www.fb18.de/gfx/28.gif[/img]

Cheers,
Frank

P.S. Im Prinzip folgt obiges L1 = L2 aber schon aus den Aequivalenzen (die urspruenglich gezeigt werden sollten). Man koennte hoechstens noch ein 6. dazu nehmen, dass der PDA bei 5. nicht fast-buchstabierend sein muss.

Schoen, danke

So langsam kann man ja anfangen, die Stunden zu zaehlen…

Nicht eingeloggt? Wie is'n das passiert? Ich fang ja an wie Frank…

/edit
veraltet



ich meinte, dass der alte automat A aufhört wenn er das alte kellerbodensymbol löscht,
der neue automat kann danach aber nun noch irgendwelche
kanten entlanglaufen, die auch im ursprungsautomaten vorhanden
waren und damit weitere buchstaben lesen
-> N(A) teilmenge L(B)


beispiel:


l = lambda, k = kellerbodensymbol .----. ----. c,k|l a,l|l ||Z1 | | '----' <--' N(A) = a* c L(B) nach dem verfahren = a* c a* denke ich mal

Es gilt wirklich N(A) = L(B).

Bei deinem Beispiel: Was hindert deinen Automaten A noch a's zu lesen, nachdem er das Kellerbodensymbol entfernt hat? Folglich auch hier:

N(A) = a* c a*

Die Definition von "mit leerem Keller akzeptierte Sprache" sagt ja nicht, dass der Automat sofort stopt, wenn er den Keller geleert hat. Es sagt doch nur, dass jedes Wort akzeptiert wird, nach dessen Lesen der Keller leer ist. Die Sprache ist dann eben nicht praefixfrei, was kein Problem ist, da es hier allgemein um PDA's geht und nicht etwa um DPDA's.

Cheers,
Frank

P.S. Nur noch 161h 16min und ein paar Sekunden [img]http://www.fb18.de/gfx/28.gif[/img]

?
das ist doch gerade die defintion der präfixfreiheit,

da bei leeren keller sofort angehalten wird,
sind die sprachen N(A) von deterministische PDA A alle präfixfrei

wie wolltest du sonst einen DPDA anschauen,
ob er nun präfixfrei ist oder nicht?


edit
ah, weil DPDA bustabierend sein müssen, ok, dann gehts,

wow, dann habe ich das ja ein jahr lang falsch gedacht,
guter hinweis muss ich sagen [img]http://www.fb18.de/gfx/22.gif[/img]

ah, weil DPDA bustabierend sein müssen, ok, dann gehts,

wow, dann habe ich das ja ein jahr lang falsch gedacht,
guter hinweis muss ich nun sagen [img]http://www.fb18.de/gfx/22.gif[/img]

Versuchs mal mit der Definition 5.10 des DPDAs…

Also, falls das noch nicht ganz klar sein sollte, betone ich das einfach nochmal:

Die Sprachfamilien der von einem PDA (OHNE D !!) mit leerem Keller und mit Endzustand akzeptierten Sprachen sind identisch!

Wenn man allerdings einen DPDA anguckt, dann sind die von einem DPDA mit Endzustand akzeptierten Sprachen eine ECHTE Teilmenge der von einem PDA akzeptierten und darueberhinaus die von einem DPDA mit leerem Keller akzeptierten Sprachen sogar eine ECHTE Teilmenge der von einem DPDA mit Endzustand akzeptierten.
(Vgl. Theoreme 5.20, 5.21, 5.25)

Cheers,
Frank <<— geht jetzt Bio-Mango zubereiten [img]http://www.fb18.de/gfx/23.gif[/img]