Erkennt der KA in der Lösung nicht eine größere Sprache als verlangt?

Question

Hallo,

ich habe mir gerade die Lösung zur Aufgabe 43 angesehen und mich gefragt, ob die akzeptierte Sprache nicht über die geforderte hinausgeht, da ich glaube, auch Wörter der Form v$v'ab bzw. das geforderte Palindrom und anschließend eine beliebige Folge von Zeichen, da gemäß der Lösung der Zustandsübergang von (s1, λ, k0) → (s2, k0) in den Endzustand s2 führt, ungeachtet, was sonst noch kommt.

Ich habe den KA im XWizard simuliert und dort wird bei Eingabe von v$v'aab das Wort akzeptiert. In der Zusammenfassung des Übungsbuches steht jedoch, dass das Eingabewort auch vollständig abgearbeitet sein muss, damit es akzeptiert wird. In diesem Fall würde die Lösung stimmen, aber der XWizard mehr akzeptieren. Ist die Lösung nun richtig und der XWizard stimmt nicht oder andersherum (oder sehe ich den Wald vor lauter Bäumen nicht mehr :)).

Sollte die Lösung stimmen, wäre meine Frage noch, ob die Überführung (s0, $, k0) → (s1, k0) nicht auch direkt in se gehen könnte, da im Falle eines Restwortes dieses ja dann nicht akzeptieren werden würde.

 

Ich hoffe, ich habe das jetzt nicht zu kompliziert formuliert.

Comments

Können Sie bitte mal das Script posten, das den Fehler verursachen soll?

---

Da ich mein Skript nicht mehr hatte, habe ich das Skript aus der Lösung kopiert und als Beispielwort $w=abbaDabbaabbb$ gewählt, was ja laut Definition nicht u$u' ist., Wenn ich nun auf "Zeige Berechnungsschritte (Latex)" klicke, wird mir angezeigt, dass das Wort akzeptiert wird, obwohl noch ein Restwort verfügbar ist und somit das Wort kein Palindrom ist.

pda:
(s1, a, a) => (s1, lambda);
(s0, D, k) => (s1, k);
(s0, D, a) => (s1, a);
(s0, b, b) => (s0, bb);
(s0, a, b) => (s0, ab);
(s0, b, a) => (s0, ba);
(s1, b, b) => (s1, lambda);
(s0, a, a) => (s0, aa);
(s1, lambda, k) => (s2, k);
(s0, D, b) => (s1, b);
(s0, b, k) => (s0, bk);
(s0, a, k) => (s0, ak);
--declarations--
e=#n#;
s0=s0;
F=s2;
kSymb=k;
inputs=abbaDabbaabbb;
simSteps=11;
maxNondetCalcDepth=12
--declarations-end--

---

Vielen Dank für den Hinweis! Sie haben recht, der XWizard hat hier einen Fehler. Das Wort dürfte nicht akzeptiert werden.

---

Ich habe den Fehler jetzt behoben, siehe hier:
http://www.xwizard.de:8080/Wizz?template=ID-11818

Answer 1

Hallo udeqy,

ich hoffe ich habe deine Frage richtig verstanden.

Der Zustandsübergang (s1, λ, k0) → (s2, k0) ist nur möglich wenn das Wort vollständig abgearbeitet (nur dann wird ein  λ gelesen) und der Keller leer ist (Kellerzeichen k0).

EDIT : Der Zustandsübergang (s1, λ, k0) → (s2, k0) ist auch möglich, wenn noch ein Restwort abzuarbeiten ist! Damit ein Kellerautomat ein Wort akzeptiert muss der Automat allerdings in einem Endzustand sein UND das Wort vollständig abgearbeitet sein (siehe auch Folie 3-5).

Der Fall (s0, $, k0) → (s1, k0) ist notwendig, wenn u´ und v´ leer sind, da in diesem Fall das Wort nur aus einem $ besteht, aber trotzdem Teil der Sprache ist.

Du kannst ja mal dein X-Wizard Skript hier posten, damit wir es nachvollziehen können.

Viele Grüße

Gregor (Tutor)

Comments

Danke für die schnelle und ausführliche Antwort.

Wenn ich es in der Vorlesung richtig verstanden habe, muss bei einem Übergang der Form (s1, λ, k0) → (s2, k0)  das Eingabewort nicht komplett abgearbeitet sein, sondern es wird einfach das aktuelle Zeichen ignoriert und nach dem Übergang dieses wieder aufgenommen. Falls dem nicht so sei, habe ich meinen Denkfehler gefunden.

---

Ich habe eben noch mal in den Folien zum Kellerautomatennachgeschaut. Du hast recht, der Übergang (s1, λ, k0) → (s2, k0) ist nach der Definition möglich, auch wenn rechts noch ein Restwort steht. Allerdings muss das Wort komplett abgearbeitet sein, damit der Kellerautomat das Wort akzeptiert (siehe Folie 3-5).

Viele Grüße
Gregor (Tutor)

Answer 2

Aha, jetzt verstehe ich, glaube ich, wo das Problem liegt! Ich muss mir das nachher noch genauer anschauen, aber das Problem ist ziemlich sicher, dass das Dollarzeichen in Latex ein reserviertes Zeichen ist. Deshalb läuft vermutlich alles schief. Hier auf der Seite übrigens auch, deshalb habe ich Ihr Skript abgeändert, sodass statt dem Dollarzeichen ein D steht.

Versuchen Sie mal bitte das veränderte Skript im XWizard - bleibt das Problem bestehen?

EDIT: Nein, das war es nicht, der XWizard behauptet tatsächlich, dass das Wort akzeptiert wird. Das ist ein Programmier-Fehler! Ich werde versuchen, das baldmöglichst zu beheben.