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

Question

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!

 

Answer 1

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!

 

Comments

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)

Answer 2

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)

 

Comments

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)

Answer 3

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!

Comments

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)