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

Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

+1 Punkt
563 Aufrufe

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

 

Gefragt 25, Sep 2015 in 2012-N-03 von uafjv uafjv Tutor(in) (167,990 Punkte)  

3 Antworten

–1 Punkt

Hallo,

A3 a)

Kann ich (s1, 1,k0) nach (s1,1k0)

              (s1,1,1) nach (s2, λ)

              (s2,λ,k0) nach (se,λ)

               anstatt

               (s1,1,k0) nach(s2,k0)

               (s2,1,k0) nach (se,k0)

Danke!

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Hi,

ja, das müsste gehen, wobei du dir keinen letzten Schritt auch sparen könntest indem du s_2 als Endzustand definierst.

Gruß,
Jonas B. (Tutor)
–1 Punkt

Ich hab mir zu der Aufgabe überlegt einfach für jede 0 zwei a's in den Keller zu schreiben und dann mit jeder 1 wieder ein a zu löschen.

Darf man prinzipiell bei einem Kellerautomaten 2 Zeichen für ein gelesenes in den Keller schreiben?

Hatte mir das ungefähr so gedacht (wahrscheinlich so nicht ganz richtig, aber dass meine Idee verständlicher wird):

(s0, 0, ko) -> (s0, aako)

(s0, 0, 0) -> (s0, aaaa)

(s0, 1, ko) -> (s2, ko)

(s0, 1, a) -> (s1, lambda)

(s1, 1, a) -> (s1, lambda)

(s1, 1, ko) -> (s2, ko)

(s2, 1, ko) -> (se, ko)

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Nein, die einzigen erlaubten Operationen auf dem Keller (für einen einzelnen Übergang) sind:

- nichts tun

- oberstes Zeichen löschen (nur bei nicht-leerem Keller)

- ein einziges Zeichen schreiben.

Deine Idee, pro 0 zwei a in den Keller zu schreiben,  könnte man vermutlich über einen zusätzlichen Zustand + λ - Übergang realisieren.

Tobias (Tutor)
–1 Punkt
Guten Morgen,

meine Idee war folgende:

1. Schreibe alle 0en in den Keller
(so,0,ko) -> (s1,0ko)
(s1,0,0) -> (s1,00)

2. Gehe wieder hoch und überschreibe dabei für jede 1 eine 0 mit einem e
(s1,1,0) -> (s1,e)

3. Sobald wieder angekommen lösche pro 1 ein e
(s1,lambda,k0) -> (s2,k0)
(s2,1,e) -> (s2, lambda)

Wäre das denn soweit zumindest korrekt?

Mein Problem ist jetzt, dass ich äquivalent zum * bei den Turingmaschinen eine Möglichkeit bräuchte zu erkennen, dass nichts mehr auf dem Kellerband steht obwohl ich "unten" bin.

Ich hoffe es wir einigermaßen klar, wo mein Problem liegt.

Vielen Dank!
Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Das funktioniert so leider nicht, da du die wesentliche Eigenschaft eines Kellers/Stacks nicht beachtest: Man kann nur auf das oberste Element zugreifen, daher funktioniert Schritt 1 noch, aber wenn direkt nach dem ersten Übergang gemäß Schritt 2 noch eine 1 eingelesen wird, dann befindet man sich in (s1, 1, e). Das e hast du ja im vorherigen Übergang geschrieben. Dafür gibt es aber keinen Übergang und der Kellerautomat würde die Eingabe nicht akzeptieren. Um an die 0er unter diesem e ranzukommen, müsstest du das e erst löschen und dann geht dir die Information verloren... Eine Möglichkeit, in den Keller runter zu "spulen" ohne die oberen Einträge zu löschen, gibt es nicht!

Tobias (Tutor)
...