vorgehensweise

Question

ich habe noch das Problem, kellerautomaten zu konstruieren.

ich kann zwar gut verstehen wie die funktionieren, aber wenn ich gefragt wurde, eine kellerautomat zu konstruieren, ich weiss nicht wie ich vorgehen muss.

Gibt es tipps oder paar wichtige Regeln, oder ein Algorithmus die man berücksichtigen soll, um den Kellerautomaten konstruieren zu können.

 

Danke im Voraus

Answer 1

Hallo ugemt!

Nein, es gibt keinen Algorithmus oder feste Vorschriften, wie man einen Kellerautomat konstruiert (außer natürlich, dass seine formale Definition der in der Vorlesung vorgestellten Form und Regeln entsprechen muss).

Das Verstehen der Funktionsweise von Kellerautomaten ist zwar nur der erste, aber dafür ein sehr wichtiger Schritt, den du ja schon gemeistert hast! Am Anfang ist es sicherlich hilfreich, sich ein paar Aufgaben durchzulesen und anschließend gründlich mit der Musterlösung auseinanderzusetzen. Dadurch bekommt man einen Eindruck davon, inwiefern man den Keller nutzen kann, um dort Informationen zwischenzuspeichern (denn das ist ja genau der Vorteil und Grund, warum wir uns mit Kellerautomaten statt mit Endlichen Automaten beschäftigen), beispielsweise das "Abzählen" gleicher Mengen an 1 und 0 in einem Wort, indem man z.B. alle 1 im Keller speichert und dann wieder rauslöscht, sobald eine 0 im Wort vorkommt.

Solche Beispiele bzw. Grundüberlegungen kann man meist auch auf andere Aufgaben übertragen, wobei natürlich meist eine gewisse Transferleistung nötig ist, was vielen Studenten am Anfang Probleme bereitet. Die Devise lautet hier ganz klar: "Übung macht den Meister". Je mehr Kellerautomaten-Aufgaben du gemacht hast, desto mehr Ideen wirst du bekommen, wie man eine Aufgabe prinzipiell lösen könnte.

Und es gibt nie die eine richtige Musterlösung! Meist können ganz verschiedene Herangehensweisen zum richtigen Ergebnis führen, d.h. zwei Kellerautomaten können ganz unterschiedlich arbeiten und trotzdem genau die gleiche Sprache erkennen!

Ich kann dir also leider keine eindeutige Antwort auf deine Frage geben, wie man Kellerautomaten generell konstruiert. Ich hoffe, dass dich meine Antwort aber trotzdem motiviert, dich weiter mit Kellerautomaten auseinanderzusetzen, und ich bin sicher, dass du mit ein wenig Übung und Ausprobieren schnell selbst Vorschritte erkennen wirst!

Viele Grüße,
Janine (Tutorin)