Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

(fehlende) Übergänge in s1

+1 Punkt
37 Aufrufe
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!
Gefragt 4, Feb 2016 in KEL-AC von uyejk uyejk Lernwillige(r) (760 Punkte)  
Bearbeitet 4, Feb 2016 von uyejk uyejk

2 Antworten

0 Punkte
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)
Beantwortet 4, Feb 2016 von uedqi uedqi Tutor(in) (108,510 Punkte)  
0 Punkte
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)
Beantwortet 4, Feb 2016 von ufdzo ufdzo Tutor(in) (102,580 Punkte)  
...