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

Auch mit deterministischem KA lösbar?

0 Pluspunkte 1 Minuspunkt
38 Aufrufe

Könnte man die Aufgabe auch mit einem deterministischen KA lösen?

Mein Ansatz ist folgender:

Ich schreibe immer nur die Einsen in den Keller (dabei gehe ich in einen Zustand s1, der nicht EZ ist). Wenn eine (erste) Null kommt, gehe ich in einen Zustand s2. Lese ich in s2 noch eine Null, wird eine Eins aus dem Keller gelöscht und ich gehe wieder in s1.
Lese ich in s2 eine Null und sehe k0, dann schreibe ich diese Null in den Keller. Bin ich in s1, lese eine Eins und sehe eine Null im Keller, so lösche ich diese Null und bleibe in s1. Sehe ich in s1 das k0 im Keller, so mache ich einen lambda-Übergang nach s0, was auch gleichzeitig mein EZ ist.

Und noch eine allgemeine Frage: Auf Folie 3-5 steht bei der Definition der partiellen Überführungsfunktion, dass man auch mehrere Zeichen auf einmal in den Keller schreiben kann (... -> S x K*) - stimmt das? Und wenn ja - wie werden diese dann ausgelesen? Als eine "Kette", oder einzeln nacheinander?

Viele Grüße!

Gefragt 13, Nov 2014 in KEL-AA von uyctv uyctv Info-Genie (21,050 Punkte)  

Eine Antwort

0 Pluspunkte 0 Minuspunkte

Am zweiten Teil deines Ansatzes muss man glaube ich noch arbeiten. So realisierst du nicht, dass zwei einsen folgen müssen, nachdem eine 0 eingelesen wurde, wenn man nur ko im Keller hat. Ist aber ohne konkrete Übergänge schwer zu sagen.

Beachte aber, dass dein KA durch den lambda-Übergang nicht deterministisch wird.

Ja, man kann auch mehrere Zeichen auf einmal in den Keller schreiben. Nachdem sie in den Keller eingetragen wurden, wird der Lese-/Schreibkopf für den Keller auf das oberste Kellerzeichen gesetzt. Das heißt nach dem Eintragen mehrerer Zeichen auf einmal weiß der KA nicht mehr, dass er dies einmal getan hat. Es wird dann immer nur das oberste Kellerzeichen betrachtet.

Viele Grüße,

Sven (Tutor)

 

Beantwortet 13, Nov 2014 von uyctv uyctv Info-Genie (21,050 Punkte)  
Okay, erstmal danke - hab ich mir schon fast gedacht, dass es schwierig ist ohne Übergänge, aber ich wollte die nicht unbedingt alle abtippen ;)
Frage zum Nichtdeterminismus
...