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!
 

 

Konfigurationsfolge lambda-Übergang

0 Punkte
558 Aufrufe

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

 

Gefragt 5, Jan 2017 in AU-2-3 von uedpn uedpn Tutor(in) (102,100 Punkte)  
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?

2 Antworten

0 Punkte

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)

Beantwortet 5, Jan 2017 von uedpn uedpn Tutor(in) (102,100 Punkte)  
Bearbeitet 5, Jan 2017 von uedpn uedpn
0 Punkte

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)

Beantwortet 5, Jan 2017 von ugehd ugehd Tutor(in) (106,130 Punkte)  
...