(fehlende) Übergänge in s1

Question

Hallo zusammen,

ich habe da noch einmal eine Frage zu den Übergängen in s1.

Warum werden nur die Übergänge (s1,a,a) und (s1,b,b) betrachtet? Es kann doch aber auch sein, dass das oberste Zeichen des Kellers a ist, wenn b auf dem Band gelesen wird bzw. b das oberste Zeichen und a auf dem Band, dann müssten die Übergänge  (s1,a,b) => (s1,lamda) und (s1.b,a) => (s1, lamda ) doch auch definiert werrden?

Dankeschön!

Answer 1

Hallo uyejk!

Nein, die von dir oben beschriebenen Fälle (a oberstes Kellerzeichen, b auf Band oder umgekehrt) sollen im Zustand s1 gerade nicht möglich sein und sind deshalb nicht als Übergänge definiert.

Wenn du sich der Kellerautomat im Zustand s1 befindet bedeutet das, dass der erste Wortteil u und das Trennzeichen $ bereits gelesen wurden und nun soll überprüft werden, ob der nun folgende Teil u' gerade der Umkehrung von u entspricht. Die Buchstaben (a und b) von u wurden zuvor (im Zustand s0) auf den Keller geschrieben und zwar nacheinander, d.h. dass das erste Zeichen von u ganz unten im Keller steht und das letzte ganz oben. Wenn du nun also überprüfen willst, ob u' gerade der Umkehrung von u entspricht, vergleichst du also das auf dem Band gelesene Zeichen (=erstes Zeichen von u') mit dem obersten Kellerzeichen (=letztes Zeichen von u). Wenn beide übereinstimmen (a=a oder b=b), dann löschst du das oberste Kellerzeichen und der Kellerautomat liest das nächste Zeichen auf dem Einganeband. Falls die beiden nicht übereinstimmen, dann ist u' nicht die Umkehrung von u und der Kellerautomat bricht somit hier ab (d.h. kein Übergang definiert), da das eingegebene Wort die Sprachdefinition u$u' verletzt.

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)

Answer 2

Hallo uyejk,

mit den vorgeschlagenen Übergängen würde der Kellerautomat nicht mehr die angegebene Sprache erkennen. Er funktioniert ja gerade so, dass er bis zum $ \$ $ -Zeichen alle Zeichen speichert, und nach dem $ \$ $ immer vergleicht, ob das oberste Kellerzeichen dem gerade gelesenen Zeichen entspricht - falls ja, wird das oberste Kellerzeichen gelöscht, falls nein hält er an und akzeptiert das Wort nicht.

Viele Grüße

Jonas (Tutor)