---

Geschrieben von mys am 30.09.2006 um 14:04:

  Kellerautomat

Hallo,

ich habe ein Problem mit dem Kellerautomat.

folgendes habe ich festgelegt:

Endzustand:1

a | # -> push | a
a | | -> push | a
a - # -> nop f
a - | -> nop 1
1 | # -> nop f
1 | | -> pop 1
1 - # -> nop f
1 - | -> nop f

Damit werden alle "Wörter" mit gleich vielen |'s vor und hinter dem Bindestrich akzeptiert (also z.B. |||-|||).

Jetzt frage ich mich allerdings warum es nicht akzeptiert wird, wenn vor dem Bindestrich mehr |'s sind als nach dem Bindestrich (also z.B. |||-||)?!
Denn die Abfolge befindet sich doch auch in Zustand 1 (Endzustand), wenn 3 |'s gepusht wurden und nur 2 |'s gepopt wurden... oder???

Das verstehe ich nicht so ganz..

Wäre toll, wenn mir das nochmal jemand genauer erklären könnte, denn in unserem Buch und im Web habe ich nichts gefunden was es mir klar werden lässt.

LG, mys

---

Geschrieben von Mazze am 30.09.2006 um 15:36:

 

Es wäre erste einmal schön wenn Du Deine Syntax die Du verwendest erklären würdest.

push/pop/nop sind klar, aber ich versteh nicht genau was Du mit

a | # meinst.

Zustand a, gelesen | und ende # ? Oder ist a der Keller?

---

Geschrieben von ed209 am 30.09.2006 um 16:07:

 

Mir geht es ähnlich wie Mazze. Gib doch mal die Zustandsmenge, das Keller- und das Eingabealphabet an. Das hilft nicht nur uns das Problem zu verstehen, sondern vermutlich dir selbst auch.

Die Schreibweise mit nop, push und pop ist mir so ehrlich gesagt auch unbekannt. Vielleicht kann mich da jemand aufklären

Gruss,
Peter

---

Geschrieben von mys am 30.09.2006 um 16:15:

 

okay..

also folgende zeile mal in worten:
a | # -> push | a

a ist der zustand in dem man sich grade befindet,
| ist das zeichen das gerade eingelesen wird,
# bedeutet der Keller ist leer

das waren die Bedingungen, wenn die erfüllt sind, dann wird folgendes gemacht:

push | bedeutet ein | dazu tun,
a ist dann wieder der zustand in den das teil danach kommt.


Hoffe es ist einigermaßen hilfreich beschrieben?!

---

Geschrieben von ed209 am 30.09.2006 um 16:26:

 

Ah ok, jetzt hab ich es verstanden. Eigentlich müsste das Wort |||-| auch erkannt werden.
Ich denke das Problem ist die Definition des Kellerautomatens. Der denn wird gerne mal unterschiedlich definiert:

Manche Kellerautomaten akzeptieren nur wenn der Keller leer ist.

Wenn du Beispiele von anderen Seiten hast, musst du aufpassen dass der Automat nicht ein bisschen anders definiert ist.

Gruss,
Peter

---

Geschrieben von mys am 30.09.2006 um 16:40:

 

also ich habe das an diesem Automatenprogramm hier ausprobiert:
Simulationsprogramm für Automaten

Vielleicht kennt den jemand und kann mir sagen, wie es bei diesem ist?
Oder muss ich das selbst noch irgendwie festlegen??

---

Geschrieben von Mazze am 30.09.2006 um 17:18:

 

Wegen

1 - | -> nop f

werden keine Wörter mit weniger | nach dem - akzeptiert.

Wegen

1 | # -> nop f

werden keine Wörter mit mehr | nach dem - akzeptiert.

Und 1 soll wirklich der Endzustand sein ja?

edit:

heißt - das - gelesen wird oder - nichts?

edit2:

wenn - wirklich - ist, ist's wirklich nach Definition ne Sache ob man bei leerem Keller terminiert oder bei vollem.

---

Geschrieben von mys am 01.10.2006 um 11:56:

 

Ja, 1 soll wirklich der Endzustand sein.

- heißt, dass - gelesen wird, es passiert aber nichts außer dass man von zustand a in zustand 1 kommt (und falls man schon in 1 is in den fehlerzustand kommt).

Habe eben mal 1 - | -> nop f und 1 | # -> nop f weg gelassen, hat nichts gebracht! Es werden immer noch nur Wörter mit gleicher Anzahl von |'s vorne und hinten akzeptiert.

Außerdem würde ich es auch gar nicht so verstehen, denn für mich heißt 1 - | -> nop f dass wenn wir im zustand 1 sind im keller ein | oben liegt und dann ein - gelesen wird, dass wir dann in den fehlerzustand kommen.

Und 1 | # -> nop f heißt für mich dass wir in zustand 1 sein, ein | gelesen wird und der keller leer ist und das nicht sein darf (also fehlerzustand).

Das hat für mich irgendwie nix damit zu tun WIE VIELE |'s nach und vor dem - sind..?!

edit: muss vielleicht der Keller im Endzustand einfach leer sein??

---

Geschrieben von Mazze am 01.10.2006 um 13:03:

 

Zitat:

muss vielleicht der Keller im Endzustand einfach leer sein??

Das haben ed und ich Dir versucht zu sagen das Kellerautomaten unterschiedlich definiert werden, und bei Deinem muss der Keller wohl leer sein.

---

Geschrieben von mys am 01.10.2006 um 14:36:

 

*lol* okay, dann sagt es auch so^^ *g*

vielen Dank für die nette Hilfe