Kellerautomat

Neue Frage »

Auf diesen Beitrag antworten »
Daniel07 Kellerautomat

Guten Tag Informatikerboard,

ich verstehe leider die Funktionsweise eines Kellerautomaten nicht genau.
Kontextfreie Grammatiken bzw. Sprachen werden als Kellerautomaten dargestellt.

Ich habe das so verstanden, dass bei jeder Eingabe eines Zeichens dieser auch in den Keller geschrieben wird. ?!

Wenn eine öffnende Klammer kommt, weiss der Automat dass auch eine schließende Klammer kommen muss zur syntaktischen Korrektheit.
Woher weiss der Kellerautomat das? Das kann es ja nur wissen, wenn alle Zeichen ebenfalls in den Keller wandern.
Woher weiss der Automat, dass bei "(" ebenfalls ein ")" kommen muss? Bei einem "a" aber nicht.
Hängt das mit meiner Grammatik zusammen? Also wenn ich z.B. diese Grammatik festlege:
S->AB
A->(B)
B->aba|epsilon?


Ich hoffe ihr könnt mir helfen.

VLG
Daniel
 
Auf diesen Beitrag antworten »
Tobias RE: Kellerautomat

Hallo,

erstmal solltest du dir vielleicht das hier durchlesen:
http://de.wikipedia.org/wiki/Kellerautomat

Zitat:
Original von Daniel07
ich verstehe leider die Funktionsweise eines Kellerautomaten nicht genau.
Kontextfreie Grammatiken bzw. Sprachen werden als Kellerautomaten dargestellt.

Kontextfreie Sprachen können durch nichtdeterministische Kellerautomaten entschieden werden.

Zitat:
Ich habe das so verstanden, dass bei jeder Eingabe eines Zeichens dieser auch in den Keller geschrieben wird. ?!

Das ist nicht richtig. In jedem Übergang (Transition) wird der Nachfolgerzustand durch das nächste Symbol auf dem Eingabeband und das oberste Symbol auf dem Keller festgelegt. Bei einem Übergang kann dann das oberste Symbol des Kellers durch ein Wort ersetzt werden. (Das Wort kann auch Epsilon sein, dann wird das oberste kellersymbol gelöscht. Es kann auch gleich dem ursprünglichen Kellerzeichen sein, dann bleibt der Keller unverändert.)

Zitat:
Wenn eine öffnende Klammer kommt, weiss der Automat dass auch eine schließende Klammer kommen muss zur syntaktischen Korrektheit.

Der Automat weiß garnichts. Je nachdem, wie der Automat festgelegt wurde, kann man mit ihm eine Sprache erkennen, die gleichviele offene wie geschlossene Klammern enthält.

Zitat:
Woher weiss der Kellerautomat das? Das kann es ja nur wissen, wenn alle Zeichen ebenfalls in den Keller wandern.

Nein. Eine einfache Strategie ist, nur offene Klammern auf den Keller zu schreiben und bei jeder geschlossenen Klammer ein Symbol wieder vom keller zu löschen. Ist der Keller am Ende leer, dann wird das Wort erkannt.


Zitat:
Hängt das mit meiner Grammatik zusammen? Also wenn ich z.B. diese Grammatik festlege:

Du musst dir klar machen, dass kontextfreie Grammatiken und nichtdeterministische Kellerautomaten dieselbe Sprachklasse (kontextfreie Sprachen) beschrreiben können. Deshalb gibt es für jede CFG einen Kellerautomat und andersrum, die dieselbe Sprache entscheidet. Wenn du zu deiner CFG einen äquivalenten nichtdet. Kellerautomaten baust und deine Grammatik die richtige Klammerung beachtet, dann tut dies natürlich dein Automat auch.
Auf diesen Beitrag antworten »
Daniel07 RE: Kellerautomat

Zitat:
Original von Tobias

Zitat:
Wenn eine öffnende Klammer kommt, weiss der Automat dass auch eine schließende Klammer kommen muss zur syntaktischen Korrektheit.

Der Automat weiß garnichts. Je nachdem, wie der Automat festgelegt wurde, kann man mit ihm eine Sprache erkennen, die gleichviele offene wie geschlossene Klammern enthält.


Wie legt man sie fest? Könntest du mir Bitte ein Beispiel nennen.


Zitat:
Original von Tobias

[QUOTE]Woher weiss der Kellerautomat das? Das kann es ja nur wissen, wenn alle Zeichen ebenfalls in den Keller wandern.

Nein. Eine einfache Strategie ist, nur offene Klammern auf den Keller zu schreiben und bei jeder geschlossenen Klammer ein Symbol wieder vom keller zu löschen. Ist der Keller am Ende leer, dann wird das Wort erkannt.


Zitat:
Original von Tobias

Du musst dir klar machen, dass kontextfreie Grammatiken und nichtdeterministische Kellerautomaten dieselbe Sprachklasse (kontextfreie Sprachen) beschrreiben können. Deshalb gibt es für jede CFG einen Kellerautomat und andersrum, die dieselbe Sprache entscheidet. Wenn du zu deiner CFG einen äquivalenten nichtdet. Kellerautomaten baust und deine Grammatik die richtige Klammerung beachtet, dann tut dies natürlich dein Automat auch.


Genau, das fehlt mir. Bitte ein Beispiel nennen.

Meinst du eine Grammatik a la:

S-AB
A-aabB
B->(B)|epsilon

Wäre das z.B. so eine Grammatik und dann eine entsprechenden nichtdet. Kellerautomaten?
Kannst du mir vielleicht zu meiner CFG oder zu einer beliebigen von dir aus ein Kellerautomaten als Beispiel nennen. Das würde mir helfen, die Thematik besser zu verstehen. Da liegen meine Probleme.

Danke
Daniel
Auf diesen Beitrag antworten »
Tobias

http://www.b.shuttle.de/b/osz-recht/theo_in/ka_3.htm

http://www.t-hollmann.de/informatik/theo...eller/index.htm

http://ls1-www.cs.uni-dortmund.de/~tick/...GTI/11-cflw.pdf

http://www.cl.uni-heidelberg.de/kurs/skr...ml/page027.html
...
 
Auf diesen Beitrag antworten »
Daniel07

Danke dir für die Links!

Ich konstruiere also keinen expliziten Kellerautomaten. Dieser wird über eine CFG festgelegt oder eine Sprache gemäß L={a^nb^n|neN} erzeugt.

Hab ich es richtig verstanden?

Ich lese es mir noch durch :-)

Gruß
Daniel
Auf diesen Beitrag antworten »
Tobias

Zitat:

Ich konstruiere also keinen expliziten Kellerautomaten. Dieser wird über eine CFG festgelegt oder eine Sprache gemäß L={a^nb^n|neN} erzeugt.


Nein. Man konstruiert sich explizit einen Kellerautomaten. Dieser Kellerautomat beschreibt eine Sprache (eben jene Wörter, die zu einem erfolgreichen Lauf im Automaten führen).

Und noch einmal:
Da CFG und nichtdeterministische Kellerautomaten gleichmächtig sind, existiert zu jeder CFG ein äquivalenter Kellerautomat. Wie der dann explizit aussieht ist eine andere Frage.
Auf diesen Beitrag antworten »
Daniel07

Also zu jeder cfg gibt es einen Nichtdeterministischen Kellerautomaten. Wenn ich eine CFG der Form:
S-> AB
A-aabB
B usw....

habe ist auch gleichzeigt mein Kellerautomat konstruiert, da es die Wörter die durch die CFG gebildet werden können verarbeiten kann. So richtig?

Wenn ich in der Form: L={a^nb^n|nelement N} eine CFSprache beschreibe, existiert auch ein Kellerautomat der diese Wörter abarbeiten kann?

Danke
Daniel
Auf diesen Beitrag antworten »
Tobias

Es gibt ein allgemeingültiges Konstruktionsverfahren, welches aus einer CFG einen nichtdet. Kellerautomaten erzeugt. Das bedeutet nicht, dass dieser Automat der einzige ist, der dazu existieren kann. Man denke z.B. an die verschiedenen Normalformen einer CFG.


Es gilt doch:

L kontextfreie Sprache <=> zu L gibt es CFG <=> zu CFG gibt es Kellerautomat

http://de.wikipedia.org/wiki/Kontextfreie_Sprache
Auf diesen Beitrag antworten »
Daniel07

Ok, mir ging es auch nicht um die KOnstruktion des Automaten sondern um das Verständnis. Automaten kommen doch nur in der Theorie vor.

Da ich im yacc eine CFG angebe und es dazu einen aquivalenten Nichtdeterm. Kellerautomaten gib, gehe ich davon aus, dass der Parser der eine CFG erhält eben so arbeitet.
Also z.B. genauso viele a`s wie b`s oder Klammer auf wie zu!

Danke dir vielmals Tobias.

Schöne Grüße
Daniel
Auf diesen Beitrag antworten »
Tobias

Auch theoretische Gebilde können konstruiert werden. Wenn man für einen Automaten seine Zustände, Endzustände, Anfangszustand und Transitionen festgelegt hat, dann ist er vollständig beschrieben.

Yacc arbeitet nicht so denn der konstruierte Automat ist nichtdeterministisch und das wäre sehr problematisch. Allerdings werden die CFG so eingeschränkt, dass man mit einem kleinen Look-Ahaed die Indeterminismen überwinden kann. Ferner konstruiert Yacc einen Automat mit mehr als einem Kellerspeicher und macht eine Bottom-Up Analyse. Wenn du die Zusammenhänge richtig begreifen willst, solltest du mal in eine Compilerbau-Vorlesung reinhören.

Schöne Grüße

Tobias
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »