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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
676 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

 

in AU-2-3 von uedpn uedpn Tutor(in) (102k Punkte)  
0 0
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 Pluspunkte 0 Minuspunkte

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)

von uedpn uedpn Tutor(in) (102k Punkte)  
Bearbeitet von uedpn uedpn
0 Pluspunkte 0 Minuspunkte

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)

von ugehd ugehd Tutor(in) (106k Punkte)  
...