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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
1.2k 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?

 

in Band I, Kapitel 5 von uyctv uyctv Info-Genie (21.1k Punkte)  
Kategorie geändert von

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
 
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.
von uyctv uyctv Info-Genie (21.1k Punkte)  
Bearbeitet von
0 0
Ähnliches gilt übrigens auch (sogar noch stärker) für Turinmaschinen, die ja eine exakte Entsprechung von Programmiersprachen darstellen.
...