Kellerautomat aus Grammatik konstruieren

Morte · Anmeldungsdatum: 01.06.2005 Beiträge: 1 Wohnort: Passau

Hi @all

!
Nachdem ich beim matheboard schon zuweilen "mitlesend" einige Probleme lösen konnte, muss ich nun doch einmal selbst eine Frage stellen, und zwar geht es um Sprachen und Automaten (eigentlich ein recht angenehmes Gebiet).

Gegeben ist folgende kontextfreie Grammatik:
G = ({S,R,F,U,T}, {x,+,*,(,)},P,S) mit P:

S -> F R
R -> + F R | epsilon
F -> T U
U -> * T U | epsilon
T -> ( S ) | x

Diese Grammatik erzeugt also korrekt geklammerte x-Ausdrücke mit * und +, z.B. ((x*x)*x+(x)).

Die Aufgabe ist nun, dazu die Überführungsfunktion eines deterministischen Kellerautomaten mit drei Zuständen anzugeben.

Ich habe schon den ganzen Tag versucht, eine Art "Umwandlungsalgorithmus" (jaja, bloß nicht denken Augenzwinkern

) zu finden, doch vergebens. Aus meinem Buch geht lediglich hervor, dass man für jede Regel "A -> alpha" (aus den Produktionen, s.o.) folgendes setzen muss:
(I) delta(z,epsilon,A) -> (z,alpha)
(II) delta(z,a,a) -> (z,epsilon) (ich vermute, für alle a aus dem Eingabealphabet?)

Wenn ich das jetzt mache, erhalte ich Folgendes:
Aus (I):
delta(z,epsilon,S) -> (z,FR)
delta(z,epsilon,R) -> (z,+FR)
delta(z,epsilon,R) -> (z,epsilon)
delta(z,epsilon,F) -> (z,TU)
delta(z,epsilon,U) -> (z,*TU)
delta(z,epsilon,U) -> (z,epsilon)
delta(z,epsilon,T) -> (z,(S))
delta(z,epsilon,T) -> (z,x)
Aus (II):
delta(z,x,x) -> (z,epsilon)
delta(z,+,+) -> (z,epsilon)
delta(z,*,*) -> (z,epsilon)
delta(z,(,() -> (z,epsilon)
delta(z,),)) -> (z,epsilon)

Doch der PDA soll ja drei Zustände haben - wie muss ich obige 12 Übergänge verändern, und reichen die überhaupt aus (oder sind überflüssige dabei)?

Danke schonmal & greetings

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Du hast ja bisher nur einen Zustand, das ist also nicht dein Problem. Ein problem aber ist, dass dein Automat nicht deterministisch ist:

1.
Die Uebergangsfunktion ist nicht eindeutig:

Gast

Danke für die Antwort!
Bisher habe ich ja gar keinen Automaten definiert - dass einer mit obiger delta-Funktion nicht deterministisch wäre, ist klar.
Einen Endzustand zu definieren ist dann auch nicht das Problem, meine Verwirrung ist eher grundsätzlicher Natur.
Ich verstehe z.B., wie man mit einem Kellerautomaten all jene Wörter erkennen kann, die "symmetrisch" sind (also z.B. aabab$babaa) - bei a legt man einfach a auf dem Stack ab, bei b eben b. Bei $ wechselt man vom Zustand z0 in den Zustand z1. In diesem Zustand führt man einfach für die entsprechenden Eingaben (b, falls b=top_of_stack, a, falls a=top_of_stack) POP aus, da so nach und nach der Keller geleert wird und am Ende leer ist => Endzustand.
Doch wie man das bei der gestellten Aufgabe hinbekommen soll, ist mir ein absolutes Rätsel, da das Wort hier nicht "symmetrisch" ist. Z.B. wäre (()(()())) kein Problem, aber (x*((x*(x+x))+x))*x+x, da versagt bei mir das intuitive Verständnis. Bei dem obigen Beispiel "sieht" man ja, wie man das Ganze hinbasteln muss, aber hier... Vielleicht bin ich zu beschränkt, oder ich hab den Knackpunkt bei der ganzen Sache doch noch nicht verstanden, jedenfalls suche ich deshalb nach einem konkreten Schema, wie man aus einer gegebenen Grammatik die Überführungsfunktion konstruiert. Hänge seit Tagen an diesem Mist fest, und bin für jeden Wegweiser aus meinem Frust-Labyrinth dankbar!!!

Greetings

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Ok der (()()())-Teil ist kein Problem. Nun zum anderen Teil:
Wie sieht es aus mit x*x+x+x*x? (also die gleiche aufgabe, ohne die Klammerung) Wieviele Zustaende in was fuer einem Automaten braeuchtest Du da?

Wenn man die Loesung auch hat, kann man das denke ich ganz gut zusammenfuegen.

ED