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

Question

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 ?

Answer 1

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)

Comments

Danke! Hat es :)