condor88 - Do 10.01.08 20:16
Titel: Kellerautomat

---

Kann mir jemand sagen, welche zustände es nach dieser definition gäbe? denn wenn ich das richtig sehe, dann hat ist dieser automat unendlich, er könnte ja unendlich viele klammerterme haben. aber sowas habe ich noch nie gemacht, bisher musste ich nur endliche Automaten basteln.

Moderiert von Narses: Tiepvehler im Titel korrigiert und das Bild in den Anhang eingefügt.

Gausi - Do 10.01.08 21:01

---

Da gibts bestimmt nen endlichen Automat zu.

Endlich heißt ja nicht, dass die erkannte Sprache endlich ist, oder die Wörter darin eine beschränkte Länge haben. Die genaue Anzahl weiß ich nicht, da müsste ich mich erstmal reindenken. Aber unendlich sind ein paar zuviel ;-)

condor88 - Fr 11.01.08 14:01

---

kann mir bitte jemand sagen, wie der Algorhythmus aussehen würde?

freak4fun - Fr 11.01.08 14:12

---

Ja, theoretisch können die unenedlich tief verschachtelt werden. :? Aber praktisch macht das ja nicht wirklich Sinn. Wie seiht denn sowas endlich aus?

Rekursion müsste dein Problem lösen.

condor88 - Fr 11.01.08 14:20

---

irgendwie habe ich an eine Rekursion gar nicht gedacht. Ist noch zu ungewohnt das Ganze...

PS: Das Problem ist gelöst, meinetwegen closed.

Fiete - Mo 14.01.08 14:38
Titel: Re: Kellerautomat

---

Mit endlichen Automaten kommst du bei dem Diagramm nicht weiter.
Um einen endlichen Automaten, der äquivalent einer Grammatik ist,
muß eine linkslineare Grammatik gegeben sein.

Aus dem Diagramm ergibt sich z.B. die Regel <Divisionsterm> --> <Zahl> / <Zahl>
also nicht linkslinear.

Fazit: mit einem endlichen Automaten ist die Aufgabe nicht lösbar.

Vielleicht hilft der Anhang weiter :les:

Gruß
Fiete

Gausi - Mo 14.01.08 14:52

---

Richtig, ein DEA würde hier nicht ausreichen, aber ein Kellerautomat sollte es tun. Der unterscheidet sich von einem endlichen Automaten ja fast nur dadurch, dass er nicht nur den Zustand zum Speichern von Informationen nutzen kann, sondern zusätzlich den Kellerspeicher/Stack. Und der hat auch nur endlich viele Zustände ;-).

Insofern ist meine Aussage von oben nicht ganz korrekt. Einen endlichen Automaten in dem Sinne gibt es hier nicht. Aber es gibt einen Automaten mit endlich vielen Zuständen, der das Problem löst.