Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Kellerautomat

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Kellerautomat

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

mys

Grünschnabel

Dabei seit: 30.09.2006
Beiträge: 5

Kellerautomat

Zitatantwort auf diesen Beitrag erstellen

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

30.09.2006 14:04

Nehmen Sie mys in Ihre Freundesliste auf

Mazze
Grünschnabel

Dabei seit: 18.09.2006
Beiträge: 7

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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Mazze: 30.09.2006 15:36.

30.09.2006 15:36

Nehmen Sie Mazze in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

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 smile

Gruss,
Peter

30.09.2006 16:07

Nehmen Sie ed209 in Ihre Freundesliste auf

mys

Grünschnabel

Dabei seit: 30.09.2006
Beiträge: 5

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?!

30.09.2006 16:15

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

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

30.09.2006 16:26

mys

Grünschnabel

Dabei seit: 30.09.2006
Beiträge: 5

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??

30.09.2006 16:40

Mazze
Grünschnabel

Dabei seit: 18.09.2006
Beiträge: 7

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.

Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von Mazze: 30.09.2006 17:23.

30.09.2006 17:18

mys

Grünschnabel

Dabei seit: 30.09.2006
Beiträge: 5

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??

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von mys: 01.10.2006 11:58.

01.10.2006 11:56

Mazze
Grünschnabel

Dabei seit: 18.09.2006
Beiträge: 7

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.

01.10.2006 13:03

mys

Grünschnabel

Dabei seit: 30.09.2006
Beiträge: 5

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

vielen Dank für die nette Hilfe Augenzwinkern

01.10.2006 14:36

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Kellerautomat