Kellerautomaten und attributierte Grammatiken

Paule · Gast

Hallo,

ich bin grad in der Vorbereitung zu ner Prüfung (theoretische Informatik) und da hätt ich doch mal zwei kleine Fragen:

1. Kellerautomaten: Es gibt die Möglichkeit per Endzustand und per leerem Keller ein Wort zu akzeptieren. Meine Frage nun, warum (!!!) lässt man deterministische Kellerautomaten per Endzustand akzeptieren?

2. attributierte Grammatiken: Soweit ist mir da alles klar. Nur wüsste ich gern mal eine Beispiel für ererbte Attribute. Mein Gedanke war, dass Typvereinbarungen ererbte Attribute sein müssten, allerdings hat mir ein Kommilitone gesagt, dass dies synthetisierte Attribute sind.
grübelnd

Ich hoffe ihr könnt mir da helfen, schon mal vielen Dank im Voraus

Gruß Paule!!

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Die Antwort zu 1. ist: Bei einem NPDA sind die Akzeptanzkriterien "leerer Keller" und "Endzustand" äquivalent, d.h. zu jedem NPDA der auf leerem Keller akzeptiert existiert ein NPDA, der mit Endzuständen dieselbe Sprache akzeptiert.

Bei einem DPDA ist diese Äquivalenz nicht gegeben. Hier sind diejenigen DPDAs, die auf leerem Keller akzeptieren auf Sprachen eingeschränkt, die keine Wörter x und y haben, so dass x ein Präfix von y ist (Präfixeigenschaft). DPDAs die mit Endzustand akzeptieren, enthalten DPDAs mit leerem Stack echt. D.h. es existieren auch Sprachen, die über leeren Stack nicht entschieden werden können jedoch per Endzustand (bezogen auf DPDAs).

Um das nochmal klar zu machen:

Sei M ein DPDA mit Akzeptanzkriterium "leerer Keller" der die Sprache L entscheidet.
Angenommen L besitze nicht die Präfixeigenschaft. Dann finden wir Wörter x, y in L mit y = xw (x ist Präfix von y).
Da M deterministisch agiert, sind die ersten |x| Zustandsübergänge auf x und auf y=xw identisch. Für x müsste M akzeptieren und auf y müsste M noch |w| weitere Schritte machen. Dies ist mit Determinismus nicht vereinbar.