 Kellerautomat |
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
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.
|
|
19.09.2007 00:03 |
|
|
Daniel07 
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
| 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
__________________
---
Gegenseitiges helfen verbindet
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Daniel07: 19.09.2007 10:07.
|
|
|
19.09.2007 10:04 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
|
|
19.09.2007 10:32 |
|
|
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
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
__________________
---
Gegenseitiges helfen verbindet
|
|
|
19.09.2007 17:21 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
| 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.
|
|
|
19.09.2007 17:25 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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
|
|
|
19.09.2007 17:45 |
|
|
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
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
__________________
---
Gegenseitiges helfen verbindet
|
|
|
21.09.2007 10:33 |
|
|
|
