Seite 1 von 1

Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 10:45
von Flora
Klausur_ws0708_loesung

Klausur_ws0405_loesung

Verfasst: 1. Sep 2011 12:16
von Flora
\\ Edit - Korrektur weiter unten

Aussagen_Zusammenfassung

Verfasst: 1. Sep 2011 12:16
von Flora
Aussagen_Zusammenfassung

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 12:34
von onbes
//EDIT

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 14:19
von Ankou
WS07/08 - 3
c) Es gibt keinen Kellerautomaten, der Palindrome erkennt, da er nicht in der Lage ist, zu erkennen, wann er die Mitte erreicht hat
Wir haben eine kontextfreie Sprache und können demnach auch einen Kellerautomaten angeben, Satz 4.1.5 im Script.
(er muss die Mitte nicht erkennen, weil nicht-deterministisch)

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 14:21
von Flora
21 Leute haben bis jetzt die Lösung für Klausur ws0405 runtergeladen und keiner hat bemerkt, dass die 1b falsch ist?^^

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 14:27
von Flora
Ankou hat geschrieben:WS07/08 - 3
c) Es gibt keinen Kellerautomaten, der Palindrome erkennt, da er nicht in der Lage ist, zu erkennen, wann er die Mitte erreicht hat
Wir haben eine kontextfreie Sprache und können demnach auch einen Kellerautomaten angeben, Satz 4.1.5 im Script.
(er muss die Mitte nicht erkennen, weil nicht-deterministisch)
Du hast recht. Habe es noch einmal nachgelesen. Ist dies dann ein passender Kellerautomat?

Bild

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 15:13
von Ankou
ich muss ehrlich sagen: ich hab keine Ahnung, ich tu mir ein bisschen schwer damit deinen PDA zu lesen auch weil die Schreibweise für mich völlig ungewohnt ist. Im Script gibt es aber nicht nur den Satz der besagt, dass ein solcher Kellerautomat existiert, sondern auch den Beweis dazu, der dir ziemlich genau und verständlich schildert wie du aus einer x-beliebigen kontextfreien Grammatik ohne nachzudenken einen PDA bauen kannst. Falls ich es korrekt gemacht habe sieht das bei mir dann so aus:
\(P=(\Sigma, Q, q_0, \Delta, A, \Gamma, X_0)\) mit
\(Q = \{q_0\},\)
\(\Gamma = \Sigma \cup \{X_0, X\},\)
\(A = \{q_0\},\)
\(\Delta = \{\)
\((q_0,X_0,\epsilon,aXa,q_0),\)
\((q_0,X_0,\epsilon,bXb,q_0),\)
\((q_0,X_0,\epsilon,a,q_0),\)
\((q_0,X_0,\epsilon,b,q_0),\)
\((q_0,X,\epsilon,aXa,q_0),\)
\((q_0,X,\epsilon,bXb,q_0),\)
\((q_0,X,\epsilon,\epsilon,q_0),\)
\((q_0,a,a,\epsilon,q_0),\)
\((q_0,b,b,\epsilon,q_0)\}\)

das heißt aber wie gesagt nicht, dass deiner falsch ist, ich hab ihn gar nicht komplett nachvollzogen

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 15:25
von Flora
Ankou hat geschrieben:ich muss ehrlich sagen: ich hab keine Ahnung, ich tu mir ein bisschen schwer damit deinen PDA zu lesen auch weil die Schreibweise für mich völlig ungewohnt ist. Im Script gibt es aber nicht nur den Satz der besagt, dass ein solcher Kellerautomat existiert, sondern auch den Beweis dazu, der dir ziemlich genau und verständlich schildert wie du aus einer x-beliebigen kontextfreien Grammatik ohne nachzudenken einen PDA bauen kannst. Falls ich es korrekt gemacht habe sieht das bei mir dann so aus:
\(P=(\Sigma, Q, q_0, \Delta, A, \Gamma, X_0)\) mit
\(Q = \{q_0\},\)
\(\Gamma = \Sigma \cup \{X_0, X\},\)
\(A = \{q_0\},\)
\(\Delta = \{\)
\((q_0,X_0,\epsilon,aXa,q_0),\)
\((q_0,X_0,\epsilon,bXb,q_0),\)
\((q_0,X_0,\epsilon,a,q_0),\)
\((q_0,X_0,\epsilon,b,q_0),\)
\((q_0,X,\epsilon,aXa,q_0),\)
\((q_0,X,\epsilon,bXb,q_0),\)
\((q_0,X,\epsilon,\epsilon,q_0),\)
\((q_0,a,a,\epsilon,q_0),\)
\((q_0,b,b,\epsilon,q_0)\}\)

das heißt aber wie gesagt nicht, dass deiner falsch ist, ich hab ihn gar nicht komplett nachvollzogen
Die Idee hatte ich auch schon, aber zumindest der 1. Schritt mit dem Kellersymbol fehlt auf jeden Fall. Es gibt immer eine Überführung der Art
\((q_0,\)#\(,\epsilon,X_0,q_0)\}\)
mit #, epsilon auf den Startzustand.
Außerdem fehlt dir eine Überführung in einen akzeptierenden Zustand \(q_1\), momentan akzeptiert er praktisch jedes/kein Wort.
\((q_0,\)#\(,\epsilon,\epsilon,q_1),\)

Laut Internet wird noch ein dritter Zustand benutzt, aber wir könnten uns vorstellen, dass es so funktioniert.

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 16:41
von dexX
Wäre nett, wenn du die Klausur noch online stellen könntest. Ich habe nur WS04/05, SS05, WS05/06, WS09/10 gefunden. Danke!

Re: Klausur_ws0708_loesung

Verfasst: 1. Sep 2011 17:07
von Ankou
Die Idee hatte ich auch schon, aber zumindest der 1. Schritt mit dem Kellersymbol fehlt auf jeden Fall.
nein - wie dir vl auffällt steht bereits im Tupel als Anfangs-Kellersymbol \(X_0\), im Script steht im Tupel noch # aber dann mit \(\# = X_0\), also quasi das selbe.
Außerdem fehlt dir eine Überführung in einen akzeptierenden Zustand q1 , momentan akzeptiert er praktisch jedes/kein Wort.
Du brauchst niemals einen zweiten Zustand, jedenfalls nicht nach unserer Definition, geht auch aus dem Beweis im Script hervor. Ich meine gelesen zu haben, dass es Definitionsfrage ist wann ein PDA akzeptiert, wir haben aber gesagt, dass ein PDA nur dann akzeptiert, wenn er in einem akzeptierenden Endzustand ist und der Kellerspeicher leer ist.
(Außerdem wird mit deiner Überführung nur das leere Wort akzeptiert, da du dich dann entscheiden musst ob du aus # ein \(X_0\) machst und geloosed hast oder ob du es lieber wegschmeißt und in den akzeptierenden Endzustand gehst ohne etwas gemacht zu haben)