Konfigurationsfolge lambda-Übergang

Question

Ich habe ein Frage zum Übungsblatt 2, Aufgabe 5:

 

Dort ist folgender det-KA definiert:

 

KA6 = ({0,1},{s0,s1},{k0,0,1},δ6,s0,k0,{s0}) 

mit δ6 :

(s0,0,k0) →(s1,0k0)

(s0,1,k0) →(s1,1k0) 

(s1,0,0) →(s1,00) 

(s1,1,0) →(s1,λ) 

(s1,0,1) →(s1,λ)

(s1,1,1) →(s1,11) 

(s1,λ,k0) →(s0,k0)

 

für das Testwort "10001110" ergeben sich folgenede Übergänge:

 

(s0,10001110,k0) -> (s1,0001110,1k0) -> (s1,001110,k0) -> (s0,001110,k0)-> (s1,01110,0k0)->(s1,1110,00k0)->(s1,110,0k0)-> (s1,10,k0)->(s0,10,k0)->(s1,0,1k0)->(s1,λ,k0)->(s0,λ,k0)

 

Ich verstehe nicht, wieso der Automat an den fett gedruckten Stellen λ ließt, aber dennoch den Zustand von s1 in s0 wechselt.

Müsste er nicht im 1. Fall eine "0" und im 2. eine "1" einlesen?

 

Vielen Dank

 

Comments

Haben Sie sich mal die Simulation im XWizard angeschaut? Dabei werden problematische Stellen oft klarer. Die ist hier verlinkt: http://www.xwizard.de:8080/Wizz?lang=ger&hide=.i2&template=ID-4502#Output

Auf den ersten Blick sehe ich gar keine Übergänge von $s_1$ aus, in denen eine $0$ oder eine $1$ bei $k_0$ im Keller gelesen werden könnte. Oder verstehe ich Ihre Frage falsch?

Answer 1

Hallo,

bei einem Kellerautomaten und dessen Zustandsübergängen, hat lambda auf der rechten und linken Seite der Definition eine unterschiedliche Bedeutung. Die beiden Seiten sind wie folgt aufgebaut (Der Zustand in dem sich der Kellerautomat befindet, das Zeichen das der Lesekopf einliest, das oberste Kellerzeichen) --> (Der Zustand in den der Kellerautomat wecheselt, die Operation die der Kellerautomat auf dem Keller ausübt). Bei den markierten Wechseln in der Konfigurationsfolge handelt es sich um folgenden Übergang: (s1,λ,k0) →(s0,k0) dieser besagt, dass der Lesekopf auf dem Zeichen auf dem er sich momentan befindet stehen bleibt (λ) und der Kellerautomat ledeglich den Zustand von s1 in s0 wechselt, ohne das sich der Lesekopf ein Zeichen nach rechts bewegt bzw. eine Operation auf dem Keller ausübt. 

Viele Grüße
Timo (Tutor)

Answer 2

lambda-Übergänge sind bei Kellerautomaten erlaubt, d.h. der Kellerautomat kann auf seinem Keller "arbeiten", ohne dass sich der Lesekopf weiterbewegt.

Man kann sich zwischen den Eingabesymbolen des Wortes beliebig viele lambdas (leere Wörter) vorstellen.

Bei dem Konfigurationsübergang (s1,001110,k0) -> (s0,001110,k0) wird folgende Überführungsfunktion verwendet: (s1,λ,k0) →(s0,k0), d.h. die erste 0 des Restwortes wird noch gar nicht verarbeitet.

Da die Überführungsfunktion (s1,0,k0) →... nicht definiert ist, ist der Kellerautomat sogar deterministisch.

Viele Grüße Philipp (Tutor)