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!
 

 

Kellerautomaten für n=2,3...

+1 Punkt
52 Aufrufe
A41 a)

 

Was mir noch nicht ganz klar ist..

 

Egal wie viele a´s wir haben, durch (s0, a,a) -> (s1, a) garantieren wir ja, dass immer nur eins übrig bleibt vor dem b, egal was unser n ist.

 

Was ich nun nicht verstehe ...

 

Für den Fall n=2 habe ich ja 2 b´s im Automaten und 4 a´s, richtig ?

 

Wenn ich nun meine a´s in den Keller geschrieben werden mit (s0, a,a) -> (s1, a), dann habe ich ja am Ende nur ein a im keller, da die restlichen einfach wegfallen.

Und dann entsteht mit dem Befehl (s1, b , a) -> (se, lambda) ein Endzustand, obwohl ich doch noch ein b habe..

 

Wo liegt mein Fehler ?
Gefragt 6, Feb 2016 in KEL-AB von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4,290 Punkte)  

Eine Antwort

0 Punkte

Hallo uqdrx!

Dein Fehler liegt darin, dass ja nicht alle 4 a's nacheinander kommen, sondern das Wort bei n=2 ja heißt : aabaab

Nun wird mit (s0,a,k0) -> (s0, ak0) das erste a in den Keller geschrieben. Mit (s0,a,a) -> (s1,a) wird, wie du selbst richtig erkannt hast, kein weiteres a in den Keller geschrieben, sondern das im Keller stehende a mit dem a, das auf dem Band gelesen wurde, überschrieben (also weiterhin nur ein a im Keller) und der Kellerautomat geht in Zustand s1 über.

So, und nun folgen eben zunächst keine weiteren a's (es gibt auch gar keinen Übergang (s1,a,a,) -> ... , denn laut Sprachdefinition dürfen nicht mehr als 2 a direkt hintereinander stehen), sondern es folgt der Übergang (s1,b,a) -> (se,lambda), durch den das eine a im Keller gelöscht wird und der Automat in den Endzustand se übergeht. Das Wort könnte hier beendet werden (n=1) oder der Prozess beginnt von vorne mit (se,a,k0) -> (s0,a), wie es im Falle n=2 geschieht.

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)

Beantwortet 7, Feb 2016 von uedqi uedqi Tutor(in) (108,510 Punkte)  
Danke! Hat es :)
...