So, ich hab jetzt auch endlich Vorlesungen 24 und 25 nachgearbeitet und kann anfangen, zu lernen. Allerdings sind mir da noch so ein paar Dinge aufgefallen. Das schlimmste ist mit [img]http://www.fb18.de/gfx/4.gif[/img] markiert. Hab Jantzen der Einfachheit halber den Link zu diesem Thread gemailt, so dass die Korrekturen auch in die Folien einfließen sollten.


Vorlesung 24:

Folie 19: [img]http://www.fb18.de/gfx/4.gif[/img]
Die Definition der Übergangsunktion erlaubt es gar nicht, in einem Schritt mal kein Zeichen vom Keller zu lesen, im Rest der Vorlesung wird das aber immer wieder getan! So wie das leere Wort bei der Eingabe explizit erlaubt wird, muss es auch beim Keller erlaubt werden.

Folie 26:
Bei der zweiten Rechnung für aaabb darf der Automat beim Übergang in z' kein neues a in den Keller schreiben. Die drei letzten Konfigurationen enthalten also alle ein a zu viel im Keller.

Folie 27:
Bei der Definition 24.8 steht am Ende z_e, da sollte z hin.


Vorlesung 25:

Folie 6: [img]http://www.fb18.de/gfx/4.gif[/img]
Bei der dort gegebenen Definition des deterministischen Kellerautomaten sind immer noch mehrere mögliche Folgezustände erlaubt, wenn mal kein Zeichen vom Keller gelesen wird.
Es sei denn, die Definition in Vorlesung 24, Folie 19 (s.o.) ist richtig, so wie sie dort steht. Dann ist aber die ganze restliche Vorlesung 24 falsch.

Folie 8: [img]http://www.fb18.de/gfx/4.gif[/img]
Dort steht, deterministische Kellerautomaten können bei leerem Keller keine weiteren Bewegungen vornehmen. Daraus könnte man schließen, dass die Definition in Vorlesung 24, Folie 19 richtig ist, der Rest von Vorlesung 24 falsch und die Definition in Vorlesung 25, Folie 6 doch richtig.

Folie 9:
Satz 25.9: Eine UND-Verknüpfung für Sprachfamilien haben wir AFAIK nicht definiert. Vielleicht hab ich's aber auch nur vergessen.
Wenn das UND-Zeichen eigentlich ein Schnittmengenzeichen sein sollte, dann stünde dort als Formel, dass jede Sprache deterministisch kontextfrei ist, die sowohl deterministisch kontextfrei als auch regulär ist. Das wäre zwar richtig, aber trivial.
In der Erklärung dazu steht dann etwas, dass man als Formel folgendermaßen ausdrücken würde:
[img]http://mokrates.de/cgi-bin/texstring?%5Cforall%20L_1%20%5Cin%20detCf%3A%20%5Cforall%20L_2%20%5Cin%20Reg%3A%20(L_1%20%5Ccap%20L_2)%20%5Cin%20detCf[/img]
Das scheint mit der UND-Verknüpfung am Anfang auch gemeint zu sein, denn dieser Zusammenhang wird auf Folie 10 für einen Beweis benutzt.

Folie 13:
Statt N(A) sollte dort wohl [img]http://mokrates.de/cgi-bin/texstring?L_%7B%5Cepsilon%7D(A)[/img] stehen.

(Anmerkungen zu 24-19, 24-26, 25-6, 25-8)

Für mich sieht das alles sehr danach aus, als wäre
einfach in den Automaten in Vorlesung 24 aus Versehen
nichts vom Keller gelesen worden.

(Das ist nämlich ein Automat aus dem F2-Skript,
und dort waren PDAs tatsächlich noch so definiert,
dass vom Keller nichts gelesen werden muss.
Das ist äquivalent zur hier gegebenen Definition,
wie man sich leicht überlegen kann (Übung! [img]http://www.fb18.de/gfx/23.gif[/img]),
macht aber hinterher Definition und Beweise für
DPDAs etwas komplizierter)

(UND-Symbol bei Sprachfamilien)

Dieses Symbol steht in dem Zusammenhang für den elementweisen
Durchschnitt von Sprachklassen, d.h.
[img]http://mokrates.de/cgi-bin/texstring?%5Cmathcal%7BC%7D%5Cwedge%5Cmathcal%7BD%7D%3A%3D%5C%7BL_1%5Ccap%20L_2%5Cmid%20L_1%5Cin%5Cmathcal%7BC%7D%2C%20L_2%5Cin%5Cmathcal%7BD%7D%5C%7D[/img],
mit dieser Definition bedeutet es also genau das, was du
geschrieben hast.

Folie 13:
Statt N(A) sollte dort wohl [img]http://mokrates.de/cgi-bin/texstring?L_%7B%5Cepsilon%7D(A)[/img] stehen.

Folie 27:
Bei der Definition 24.8 steht am Ende z_e, da sollte z hin.

Das denke ich auch.

(Wieder mal Insiderinfo: N(A) war übrigens die alte
Bezeichnung für die mit leerem Keller akzeptierte
Sprache [img]http://www.fb18.de/gfx/28.gif[/img]).

Als kleine Anmerkung: solche Hinweise und Fragen zum Skript bzw. zu Folien sind eigentlich bei den Veranstaltern gern gesehen (zumindest habe ich es so erlebt). Die kann man ihnen auch mal direkt zukommen lassen, damit sie ihr Skript verbessern können. [img]http://www.fb18.de/gfx/23.gif[/img]

Das ist nämlich ein Automat aus dem F2-Skript,
und dort waren PDAs tatsächlich noch so definiert,
dass vom Keller nichts gelesen werden muss.

bin da jetzt nen bisschen verwirrt: dürfen wir jetzt das leere Wort vom Keller oder von der Eingabe lesen oder nicht?

Als kleine Anmerkung: solche Hinweise und Fragen zum Skript bzw. zu Folien sind eigentlich bei den Veranstaltern gern gesehen (zumindest habe ich es so erlebt). Die kann man ihnen auch mal direkt zukommen lassen, damit sie ihr Skript verbessern können. [img]http://www.fb18.de/gfx/23.gif[/img]

Das hat er doch gemacht:

Hab Jantzen der Einfachheit halber den Link zu diesem Thread gemailt, so dass die Korrekturen auch in die Folien einfließen sollten.

Hab Jantzen der Einfachheit halber den Link zu diesem Thread gemailt, so dass die Korrekturen auch in die Folien einfließen sollten.

Herr Jantzen liest das hier ohnehin mindestens einmal in der Woche…

Herr Jantzen liest das hier ohnehin mindestens einmal in der Woche…

hat er und das Angesprochene ist geändert worden,
so wie >georg< das richtig erkannte!

M.J.

das Angesprochene ist geändert worden,

Kleine Anmerkung noch zu Vorlesung 24:
Auf Folie 21 wird noch Epsilon vom Keller gelesen
und auf Folien 25,26 muss noch eine Kante a,#|a#
von z nach z hinzugefügt werden.

bin da jetzt nen bisschen verwirrt: dürfen wir jetzt das leere Wort vom Keller oder von der Eingabe lesen oder nicht?

Das leere Wort von der Eingabe lesen (d.h. in irgendeinem Schritt mal nichts von der Eingabe lesen) ist erlaubt.
Vom Keller muss jetzt immer etwas gelesen werden. Das lässt sich in den meisten Fällen dadurch kompensieren, dass man statt einer Transition ohne gelesenes Kellerzeichen einfach für jedes Kellerzeichen eine Transition einbaut, die das Kellerzeichen liest und gleich wieder schreibt - aber wenn der Keller bereits leer ist, geht das nicht und der Automat hält zwangsläufig an. Das ist der einzige Unterschied zur alten Definition - der Automat kann nicht mehr weiterarbeiten, wenn der Keller leer ist.

Nachtrag: Hab mal in die Folien geguckt - neben dem, was georg schon sagte, ist auch die 2. Rechnung in Vorlesung 24, Folie 26 noch nicht korrigiert (ab dem Übergang zu z' ist ein a zuviel auf dem Keller).
Und der Beweis in Vorlesung 25, Folie 2 liest auch noch klein-Epsilon vom Keller. Außerdem sind dort Folgezustand und zu schreibendes Bandwort in den Tupeln konsequent vertauscht. Der Folgezustand sollte laut unserer Definition zuerst kommen.

Vorschlag: Wäre es nicht einfacher, [img]http://mokrates.de/cgi-bin/texstring?(z'%2C%20x%2C%20w)%20%5Cin%20%5Cdelta(z%2C%20x%2C%20%5Cepsilon)[/img] als Abkürzung zu definieren für: [img]http://mokrates.de/cgi-bin/texstring?%5Cforall%20X%20%5Cin%20%5CGamma%3A%20(z'%2C%20x%2C%20wX)%20%5Cin%20%5Cdelta(z%2C%20x%2C%20X)[/img]? Dann müsste man weniger umändern und wir könnten das auch in der Klausur benutzen. Wäre nicht mal ein Problem für deterministische Automaten - eine extra-Bedingung für Determinismus wie beim Lesen des leeren Wortes von der Eingabe müsste man nicht mal einführen, da sich das schon aus der 1. Bedingung ergibt (ich spreche von Vorlesung 25, Folie 6).
Dann hätte man wirklich keinen Unterschied mehr zu vorher, außer, dass der Automat wie gewünscht bei leerem Keller immer anhält.

PS: An dieser Stelle mal vielen Dank an georg, dass Du in FGI-Fragen immer so schnell zur Stelle bist! [img]http://www.fb18.de/gfx/23.gif[/img]

Kleine Anmerkung noch zu Vorlesung 24:
Auf Folie 21 wird noch Epsilon vom Keller gelesen
und auf Folien 25,26 muss noch eine Kante a,#|a#
von z nach z hinzugefügt werden.

auch das wurde noch schnell, am 16.07., geändert!

M.J.

Vorschlag: Wäre es nicht einfacher, [wurde nicht mit kopiert] als Abkürzung zu definieren für: [wurde nicht mit kopiert]? Dann müsste man weniger umändern und wir könnten das auch in der Klausur benutzen.

Das oberste Kellersymbol wird m.E. immer links notiert, dh.,
als "Epsilon-auf-Keller-Lesen-Ersatz" sollte dies:
[img]http://mokrates.de/cgi-bin/texstring?$%5Cforall%7BX%5Cin%5CGamma%7D:(z',Xw)%20%5Cin%20%5Cdelta(z,x,X)$[/img] stehen!
(Da die Eingabe nur gelesen wird, steht sie im Bild von delta nicht mehr drin!)

Aber:
Das jetzt als offizielle Änderung, sooo kurz vor der Klausur - und nur hier - bekanntgeben zu wollen, halte ich für ungeeignet!
In der Klausur kann Jede/r diese Abkürzungsnotation doch hinschreiben und dann verwenden!
Solches geht doch immer:
Eigene Definition
1. Erklären und dann (erst)
2. benutzen.

Das oberste Kellersymbol wird m.E. immer links notiert

Richtig, deshalb habe ich das auch so definiert, dass, wenn man kein Zeichen vom Keller liest und dann w auf den Keller schreibt, das w auch oben liegt und nicht das Zeichen X, was wir ja eigentlich gar nicht gelesen haben. Meine Definition war schon richtig so.

Das jetzt als offizielle Änderung, sooo kurz vor der Klausur - und nur hier - bekanntgeben zu wollen, halte ich für ungeeignet!

Die Korrektur der Folien hat ja auch erst kurz vor der Klausur stattgefunden, in so ziemlich allen selbstgedruckten Scripten gibt es immer noch die ganzen Beispiele, in denen \epsilon vom Keller gelesen wird - es wäre also eher ein Vorteil als ein Nachteil für diejenigen, die hier nicht mitlesen.

In der Klausur kann Jede/r diese Abkürzungsnotation doch hinschreiben und dann verwenden!

Ja, das geht natürlich. Eine offizielle Definition hätte den Vorteil, dass man sich die Definition der Abkürzung in der Klausur erspart.

Aber jetzt ist es wirklich ziemlich spät. War ja nur so 'ne Idee.