Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Deterministische kontextfreie Sprachen » Präfixeigenschaft
Akzeptanzbedingungen deterministischer Kellerautomaten Deterministische kontextfreie Sprachen Beispiele für deterministische kontextfreie Sprachen
Unterabschnitte

Präfixeigenschaft

Weil der Keller bei DKAs leer läuft, ist das Präfix des zu untersuchenden Wortes schon selbst ein Wort der Sprache, benötigen wir die Präfixeigenschaft für alle Wörter der Sprache. Das bedeutet, daß in der Sprache ein Wort niemals echtes Präfix eines anderen Wortes ist.

Definition Präfixeigenschaft

Sei $L\subseteq\Sigma^{*}$. $L$ hat die Präfixeigenschaft, wenn für alle Wörter $w\in L$ gilt:
Ist $x$ ein echtes Präfix von $w$ so gilt $x\notin L$

Deterministische kontextfreie Sprachen mit Präfixeigenschaft werden von DKAs mit Leerer-Keller-Akzeptanz entschieden

Sei $K$ ein DKA
  1. $L_{\epsilon}(K)$ ist deterministisch kontextfrei, d.h. $L=L(K')$ für einen DKA $K'$.
  2. $L_{\epsilon}(K)$ hat Präfixeigenschaft
  1. Wenn wir aus einem DKA eine Grammatik machen und dann aus dieser wieder einen NKA, so ist die auch ein DKA.
  2. Falls die Sprache keine Präfixeigenschaft hat, also $w=xy$ und $w,x\in L_{\epsilon}(K)$, so verwirft die DKA bei leerer Kellerakzeptanz in der Konfiguration

    \begin{displaymath}(q,y,\epsilon)\end{displaymath}

    wenn der Keller leer ist. Wenn aber die Sprache Präfixeigenschaft hat, so läuft die DKA mit Leerer-Keller-Akzeptanz bis zum Ende.
Also akzeptieren DKAs mit Leerer-Keller-Akzeptanz nur deterministisch kontextfreie Sprachen mit Präfixeigenschaft.


Des weiteren gibt es auch zu jeder deterministischen kontextfreien Grammatik mit Präfixeigenschaft einen DKA mit Leerer-Keller Akzeptanz.

Um dies zu beweisen simulieren wir den DKA mit einem DKA mit Leerer-Keller-Akzeptanz. Wir legen zu Beginn das Symbol $\bot$ auf den Stack. Geraten wir ein einen Endzustand, so entleeren wir den Stack ganz, so daß der DKA akzeptiert. Es ist klar das ein solcher simulierender DKA eine deterministische kontextfreie Grammatik mit Präfixeigenschaft akzeptiert, da der Keller niemals ganz leer wird, sondern das nur am Ende tut.

Akzeptanzbedingungen deterministischer Kellerautomaten Deterministische kontextfreie Sprachen Beispiele für deterministische kontextfreie Sprachen