Ich grübel gerade über die Bemerkung nach dem Lemma 5.13 (Seite 122 oben), bei dem es um die Konstruktion eines Automaten B geht, der mit leerem Keller die gleiche Sprache akzeptiert wie der Automat A mit Endzustand. Dort steht nämlich, dass die beiden Automaten A und B nicht äquivalent seien.
Um dies zu überprüfen ergibt sich sofort das Problem, dass Z'end nirgendwo (weder Script noch Folien) definiert wurde (würde es dafür nicht in der Klausur Punktabzüge geben? [img]
http://www.fb18.de/gfx/17.gif[/img]). Ich nehme mal an, dass bei dem Aufstellung der o.g. Behauptung (L(A)!=L(B)) einfach vorausgesetzt wurde, dass Z'end leer ist (dann würde L(B) natürlich leer sein). Aber wenn man Z'end=Zend oder Z'end={z_empty} setzt, dann sollten doch die PDAs A und B äquivalent sein (da dann L(B)=N(B) ist), oder?
Dort steht nämlich, dass die beiden Automaten A und B nicht äquivalent seien
Das ist korrekt: Äquivalenz war nur zwischen PDA's definiert, die mit Endzustand akzeptieren!!
Also kann man von N(A) bei einem PDA sprechen, der keine Endzustände besitzt.
Wenn dann N(A) = L(B) für einen anderen PDA (mit Endzuständen also) gilt, so ist das nett.
TROTZDEM sagen wir (formal, nach unserem Skript) nicht, dass A und B äquivalent sind.
(ich sagte das recht deutlich in der Vorlesung.)
Merken Sie sich solche Fragen auch für das Schnell-Tutorium am 14.7.
Ich antworte hier jetzt erst einmal nicht mehr,
M.J.
Ja okay. Danke erstmal. Aber mir ist klar, dass die Automaten nicht äquivalent sind, wenn der eine keinen Endzustand hat.
Allerdings ist die Menge der Endzustände zu diesem Automaten im Script nirgendwo angegeben. Wenn da wenigstens stehen würde, dass sie leer ist, dann würde ich Ihnen ja recht geben. Aber so ist das ja eher gerate. Deswegen finde ich, dass man nicht so einfach behaupten kann, dass die beiden Automaten nicht äquivalent sind, weil zu dieser Aussage einfach die benötigten Informationen fehlen.
Umgekehrt wäre es ja ganz einfach die Automatenkonstruktion so zu machen, dass die beiden Automaten _immer_ äquivalent sind, indem man z'_end = {z_empty} wählt.
Wenn da wenigstens stehen würde, dass sie leer ist, dann würde ich Ihnen ja recht geben.
Ok, dass da immer noch kleine Unsauberkeiten im Skript sind,
sehe ich hierdurch nicht zum ersten Mal, wird für die Zukunft auch korrigiert!
In diesem Sinne danke ich allen, die (auch auf diesem Weg) für Verbesserungen sorgen.
Also auch Dank an "korelstar" von "theorinix"
Aber so ist das ja eher gerate. Deswegen finde ich, dass man nicht so einfach behaupten kann, dass die beiden Automaten nicht äquivalent sind, weil zu dieser Aussage einfach die benötigten Informationen fehlen.
Im Skript soll insbesondere betont werden, dass man L(A) = N(B) nicht als Begründung für Äquivalenz benutzen darf!
Wenn du den Automaten B, also hier vorallem die Menge Z'_{end}, so definierst, dass N(B) = L(B) also insgesamt auch L(A) = L(B) gilt, so sind die Automaten sogar äquivalent (du hast recht, dass das mit Z'_{end} = {z_{empty}} zu erreichen ist), aber das ist hier gar nicht so wichtig, es ging darum einen Automaten B zu konstruieren, der mit leerem Keller gerade die Sprache akzeptiert, die A mit Endzustand akzeptiert. Welche Sprache B mit Endzustand akzeptiert ist so gesehen egal, es geht darum welche Sprache mit leerem Keller akzeptiert wird!
Noch eine Anmerkung: Für den PDA B wird $ als Kellerbodensymbol eingeführt. Daher muss die (Teil-)Kantenmenge K_1 wie folgt lauten:
K_1 := { (z_{begin}, \lambda, $, \bottom $, z) | z \in Z_{start}}
Sonst kann der Automat B, dessen einziger Startzustand z_begin ist nämlich nichts tun (da anfänglich $ im Keller ist).
Alternativ: Statt $ weiterhin \bottom als Kellerbodensymbol des PDA B und in K_1 das vierte Element im Tupel von "$ \bottom" in "\bottom $" ändern (dann liegt $ wieder ganz unten im Keller).
Cheers.
P.S. Man kann dies auch umgekehrt beweisen, womit dann letztendlich gezeigt ist, dass die beiden Akzeptierungsmethoden (mit leerem Keller oder mit Endzustand) für PDAs äquivalent sind. Für DPDAs gilt dies allerdings nicht!
