Wann bei Kellerautomat Zustand wechseln?

Question

Hallo,

ich habe noch ein Problem mit den Zustandsübergängen bei Kellerautomaten. Ich bin mir oft nicht sicher, wann genau ich meinen Zustand wechseln muss. Gibt es da irgendeine "Faustregel", an die ich mich halten kann?

 

Answer 1

Eine richtige Faustregel gibt es da leider nicht. Wie ich schon einmal bzgl. Grammatiken geschrieben habe, ist das ein bisschen, als würde man fragen, ob es eine Faustregel dafür gibt, wie viele Zeilen ein Java-Programm haben soll oder wann man eine neue Variable einführen sollte (oder etwas ähnliches)... Die Frage, wie man den einfachsten Kellerautomaten (oder sogar irgendeinen) für eine beliebige Sprache angibt, ist ungelöst. Es ist immer ein Trade-off zwischen Kodieren von Informationen im Keller und in den Zustandsübergängen (wobei man ganz ohne den Keller normalerweise nicht auskommt, weil ein Kellerautomat ohne Keller äquivalent zu einem endlichen Automaten ist). Wie viele Zustände man braucht, ist aber im Vorfeld im Allgemeinen nicht zu beantworten und Teil der Fragestellung.

Sie sollten immer im Kopf haben, wie viele "verschiedene Modi" (was auch immer das im einzelnen bedeutet) Ihr KA haben soll, und dann für jeden Modus einen Zustand einführen. Typischerweise könnte ein KA etwa in einem Modus Zeichen in den Keller schreiben und sie in einem zweiten wieder lesen und herauslöschen. Oft gibt es einen separaten Zustand als Endzustand, vor allem dann, wenn das leere Wort nicht in einer Sprache enthalten ist und deshalb der Anfangszustand nicht gleichzeitig Endzustand sein darf; oder wenn die Nutzung eines vorhandenen Zustands als Endzustand zu einer unzulässigen Schleife führen würde.

Wenn wir so eine Frage in der Klausur stellen, ist immer auch Ihre Kreativität gefragt. Man kann das aber gut trainieren, da wir eigentlich immer ähnliche (und verhältnismäßig einfache) Sprachen für solche Aufgaben verwenden. Schauen Sie sich also am besten unsere Übungsaufgaben an, bis Sie den Dreh raushaben.

Viele Grüße

Lukas König

PS. Konkretere Hinweise können wir Ihnen geben, wenn Sie sich auf eine spezielle Aufgabe beziehen. Stellen Sie die Frage dann einfach in der entsprechenden Kategorie.

Comments

Ähnliches gilt übrigens auch (sogar noch stärker) für Turinmaschinen, die ja eine exakte Entsprechung von Programmiersprachen darstellen.