Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kellerautomat Verständnisfrage
Servus!
Ich habe eine Frage zum Kellerautomaten der Präsenzaufgabe 53. (Mitschrift ist im Anhang).
In den ersten 5 Regeln ist es egal, was auf dem Band steht, wir lesen es nicht. (Epsilon)
In der letzen Regel ist auch egal was auf dem Band steht, wir lesen Z0 auf dem Stack, und gehen in den akzeptierenden Endzustand.
Was ist, wenn die Eingabe z.B. “abca” ist? Wird diese dann fälschlicherweise akzeptiert?
Imo schon, da wir ja zuerst für eine geeignete Belegung, “aBC” auf den Stack schreiben,
“a” auf Band und Stack lesen/entfernen, “B” durch “b” ersetzen, lesen/entfernen, “C” durch “c” ersetzen, lesen/entfernen,
und dann auf dem Stack Z0 steht, und somit der Automat in q2 übergeht, obwohl noch ein a auf dem Band steht.
Kann mich da wer aufklären?
Grüße
Nenas
Attachment:
Kellerautomat.jpg: https://fsi.cs.fau.de/unb-attachments/post_127442/Kellerautomat.jpg
Schau mal in die Definition des Kellerautomaten. Ich meine mich zu erinnern, dass der nur akzeptiert, wenn das Eingabeband leer ist.
Stimmt, sollte aufmerksamer lesen. Finde aber die Bezeichnung F: “Akzeptierende Zustände” dann sehr verwirrend…
Danke dir!
Wörter werden bei PDAs eben durch Erreichen einer akzeptierenden Endkonfiguration akzeptiert, nicht „bloß“ durch akzeptierende Zustände. 
MfG
Rolf Wanka
1 Like