Hi!
Bin beim Googlen auf Euer Forum gestoßen und ich muss sagen, das scheint eine ziemlich coole Angelegenheit zu sein. Ich studiere in Bremen, aber ich hoffe mal es ist trotzdem in Ordnung wenn ich Euch eine kurze Frage stelle.

In einer Übung sollen wir einen Kellerautomaten bauen, der folgende Sprache erkennt:

L = {w element {a,b}* | w enthält doppelt so viele a's wie b's}

Mit zwei Gruppen haben wir gestern darüber nachgedacht wie man diesen Automaten am besten baut. Das ganze hat etwa zwei Stunden gedauert (Ganz schön nervig, wenn die Kommunikation dabei nur aus "er liest ein a (b) schreibt ein a (nix) in den Stack und geht über zu …" besteht) und dazu geführt, dass wir einen Automaten mit 5 Zuständen und 17 Übergängen hatten. Gestern Abend habe ich dann mal etwas herumgesucht und ein Programm (JFLAP) gefunden mit dem ich testen konnte, ob es funktioniert. Dabei stellte ich dann fest, dass "baa" und "aba" erkannt wurden, "aab" allerdings zum Beispiel überhaupt nicht.

Das kann eigentlich alles nicht so kompliziert sein, wie wir uns das gemacht haben, aber mir fehlt irgendwie der zündende Gedanke, wie man da am schlausten vorgeht.

Falls mir da jemand einen kleinen Tipp geben könnte, würde ich mich sehr freuen.

5 Zustände und 17 Übergänge ist gar nicht mal so viel,
aber ohne Konzept hilft das natürlich nicht,

mir fällt da ein Automat mit 2 Zuständen und 8 Übergängen ein,
(vielleicht nicht deterministisch usw.)
aber komplett verraten find ich nicht so lustig

erst mal ein Tipp:
der 2. Zustand ist nur der Endzustand, zu dem man mit leeren Keller gelangt,
alles andere kann man mit Schleifen im Startzustand erreichen,
und so viele gibts da gar nicht,
entweder man liesst ein a ober ein b,
und je nachdem was im Keller steht braucht man halt mehrere Kanten jeweils,

im Keller muss der genaue Zustand des bisher gelesenen Wortes stehen
(also die Differenz von der Anzahl a und Anzahl b),

wenn mehr a als b im bisher gelesenen Wort sind,
dann kann man das genau aus dem Kellerinhalt rauslesen,
andersrum auch,

man braucht also nur ne intelligente Speicherung der Differenz,
da kannst du ja erst noch mal überlegen


Beispiel:
Wort: ababbaaaa

bisher gelesenes Teilwort: a
im Keller steht: (indirekt:) ein a und ein b noch benötigt

bisher gelesenes Teilwort: ab
im Keller steht: ein a noch benötigt

bisher gelesenes Teilwort: aba
im Keller steht: leer, könnte jetzt terminieren

bisher gelesenes Teilwort: ababb
im Keller steht: noch 4 a benötigt

usw.

Hey, danke, Du bist ein Genie! :)

Hab da etwas drüber nachgedacht und nun klappt es.

Das Problem war einfach, dass wir erstens nur a's in den Keller geschrieben haben und zweitens immer nur geguckt haben, ob EIN a im Keller ist bzw. der Keller leer ist (nur wenn ein b gelesen wurde, haben wir versucht zwei a zu löschen). So konnte das ja auch eigentlich nicht funktionieren. Sind wir jedenfalls zu Viert nicht drauf gekommen, dass man vielleicht immer zwei Zeichen im Stack betrachten sollte.

Jetzt verstehe ich den Sinn des Ganzen auch besser…

Vielen Dank nochmal,
Sleepy