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

Schöne Ferien!
 

 

Wann bei Kellerautomat Zustand wechseln?

+1 Punkt
937 Aufrufe

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?

 

Gefragt 13, Nov 2014 in Band I, Kapitel 5 von uyctv uyctv Info-Genie (19,150 Punkte)  
Kategorie geändert 25, Dez 2014 von Lukas König

Eine Antwort

0 Punkte
 
Beste Antwort
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.
Beantwortet 13, Nov 2014 von uyctv uyctv Info-Genie (19,150 Punkte)  
Bearbeitet 25, Dez 2014 von Lukas König
Ähnliches gilt übrigens auch (sogar noch stärker) für Turinmaschinen, die ja eine exakte Entsprechung von Programmiersprachen darstellen.
...