Kellerautomat aus Grammatik <-> Grammatik aus Kellerau

Nixblicker · Gast

Hallo Leute,

ich habe 2 Probleme!

1. Ich verstehe nicht wie man aus einer Grammatik zu einem Kellerautomaten kommt:

Hier mal die Grammatik:

G = ({S,X}, {a, b, c}, P, S) mit den Produktionen
S −> bX|aS ,
X −> bS|c

1. mit leerem Keller 2. ohne leeren Keller
Leider keine Ahnung wie das geht! Bitte Bitte helfen!

2. Ich verstehe nicht wie man aus einem Kellerautomaten zu einer Grammatik kommt:

Hier mal der Kellerautomat:

A = ({s, q}, {0, 1}, {A,B}, , s, A, Augenzwinkern

der Kellerautomat mit der Übergangsrelation :
s 1 A BA s
s 1 B BB s
s 0 B B q
s € A € s
q 1 B € q
q 0 A A s

wobei € das leere Wort darstellen soll!

Vielen Dank im Voraus!

peter pan · Gast

also du musst die treppe runter gehen um in den keller zu kommen

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Also um aus einer Grammatik einen Kellerautomat mit Akzeptanzkriterium "leerer Keller" zu machen brauchst du nur einen einzigen Zustand q mit einer Schlinge und ein Kellerbodensymbol S (der Startzustand der Grammatik).

Die Schlinge beschriftest du dann gemäß Produktionsregeln:

Beispiel:

S −> bX|aS ,
X −> bS|c

Schlingenbeschriftung:
(Notation: Zeichen vom Wort, Kellersymbol Lesen | Kellersymbol schreiben

Epsilon, S | bX
Epsilon, S | aS
Epsilon, X | bS
Epsilon, X | c
a, a | Epsilon
b, b | Epsilon
c, c | Epsilon

Erklärung:
Am Anfang baust du dir aus dem Bodenkellersymbol nichtdeterministisch das Wort im Keller auf, das du als Eingabe bekommen hast. Dies ist möglich, weil man die ganze Zeit Epsilon-Wege geht ohne das eigentliche Eingabewort zu lesen.
Danach löscht du die Terminalsymbole der Reihe nach so wie sie kommen aus dem Keller und der Kellerspeicher ist dann leer. Ergo: Das Wort wird akzeptiert.