Klausur_ws0708_loesung

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Klausur_ws0708_loesung

Beitrag von Flora » 1. Sep 2011 10:45

Klausur_ws0708_loesung
Dateianhänge
ws0708_loesung.pdf
(294.24 KiB) 301-mal heruntergeladen
Zuletzt geändert von Flora am 1. Sep 2011 12:17, insgesamt 1-mal geändert.

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Klausur_ws0405_loesung

Beitrag von Flora » 1. Sep 2011 12:16

\\ Edit - Korrektur weiter unten
Zuletzt geändert von Flora am 1. Sep 2011 14:24, insgesamt 1-mal geändert.

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Aussagen_Zusammenfassung

Beitrag von Flora » 1. Sep 2011 12:16

Aussagen_Zusammenfassung
Dateianhänge
Aussagenzusammenfassungen.pdf
(417.71 KiB) 221-mal heruntergeladen

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Klausur_ws0708_loesung

Beitrag von onbes » 1. Sep 2011 12:34

//EDIT

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Klausur_ws0708_loesung

Beitrag von Ankou » 1. Sep 2011 14:19

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)
Zuletzt geändert von Ankou am 1. Sep 2011 14:24, insgesamt 1-mal geändert.

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Re: Klausur_ws0708_loesung

Beitrag von Flora » 1. Sep 2011 14:21

21 Leute haben bis jetzt die Lösung für Klausur ws0405 runtergeladen und keiner hat bemerkt, dass die 1b falsch ist?^^
Dateianhänge
ws0405_loesung.pdf
Korrektur
(475.08 KiB) 204-mal heruntergeladen

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Re: Klausur_ws0708_loesung

Beitrag von Flora » 1. Sep 2011 14:27

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

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Klausur_ws0708_loesung

Beitrag von Ankou » 1. Sep 2011 15:13

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

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Re: Klausur_ws0708_loesung

Beitrag von Flora » 1. Sep 2011 15:25

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.

dexX
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 19. Okt 2009 16:07

Re: Klausur_ws0708_loesung

Beitrag von dexX » 1. Sep 2011 16:41

Wäre nett, wenn du die Klausur noch online stellen könntest. Ich habe nur WS04/05, SS05, WS05/06, WS09/10 gefunden. Danke!

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Klausur_ws0708_loesung

Beitrag von Ankou » 1. Sep 2011 17:07

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)

Antworten

Zurück zu „Archiv“