Warum wird das leere Wort nicht akzeptiert?

Question

Hallo, 

ich verstehe hier aber nicht warum das leere wort nicht auch vom KA akzeptiert wird, das doch steht w Element (a,b,$)*. Der stern bedeutet, dass das leere Wort akzeptiert wird oder?

Außerdem wollte ich fragen ob meine Variante auch stimmt:

(s0,a,k0) --> (s1,ak0)

(s0,b,k0) --> (s1,bk0)

(s1,a,a) --> (s1,aa)

(s1,a,b) --> (s1,ab)

(s1,b,b) --> (s1,bb)

(s1,b,a) --> (s1,ba)

(s1,$,k0) --> (s3,k0) ( warum wird hier in der Musterlösung nicht in den Endzustand s2 gewechselt?)

(s1,$,a) --> (s2,a)

(s1,$,b) --> (s2,b)

(s2,b,b) --> (s3,lambda)

(s2,a,a) --> (s3,lambda)

(s3,lambda,k0) --> (s3,k0)

 

s3 ist mein Endzustand. 

 

Vielen Dank im Voraus.

Answer 1

Hey ukdxs,

zunächst mal zu deiner ersten Frage: Bei der Sprachdefinition ist es extrem wichtig, dass du diese immer komplett betrachtest und nicht anhand vom * bzw. + im ersten Teil schon davon ausgehst, dass das leere Wort in der Sprache ist bzw. nicht. Im linken Teil werden die Zeichen definiert aus denen die Wörter bestehen (hier a,b,\$) und zunächst das leere Wort eingeschlossen. Für sämtliche Wörter aus dieser Menge muss die Bedingung die folgt jedoch noch zutreffen (Palindrom mit Dollar-Zeichen in der Mitte). Nur dann sind sie auch Wörter der Sprache. Da dies für das leere Wort nicht zutrifft, gehört es auch nicht zu der Sprache.

Nun zu deinem Automaten:
Die Zustandsüberführungsfunktionen für s2 sind nicht korrekt. Sobald das erste Zeichen nach dem Dollar-Zeichen mit dem letzten Zeichen vor dem Dollar-Zeichen übereinstimmt, springt dein Automat in s3 ohne restlichen Zeichen zu überprüfen. Man darf hier also nicht direkt in den Endzustand springen.
Zudem ist deine letzte Funktion einer Art Endlosschleife für den Automaten. Ist er in s3 und k0 im Keller, bleibt er in s3 und änder nicht im Keller. Und die Funktion wird wieder ausgeführt. Daher wird bei der Musterlösung ein weiterer Zustand als Endzustand genutzt. In diesen könnte man, meiner Meinung nach, wenn der Automat in s1 ist, \$ eingelesen wird und k0 im Keller steht auch direkt springen.

Ich hoffe ich konnte deine Fragen beantworten!

Viele Grüße
Ashvin