Deterministisch kontextfreie Sprachen

Jede Sprache, die von einer kontextfreien Grammatik erzeugt wird, wird von einem nichtdeterministischen Stackautomaten erkannt.

Die Frage ist nun, ob es vielleicht sogar auch einen deterministischen Stackautomaten gibt, der die Sprache erkennt. Oder anders gefragt: Werden alle kontextfreien Sprachen von deterministischen Stackautomaten erkannt?

Bei den regulären Sprachen, also denjenigen Sprachen, die von regulären Ausdrücken erzeugt werden, ist es ja so. Jede reguläre Sprache wird von einem nichtdeterministischen endlichen Automaten erkannt und auch sogar von einem deterministischen endlichen Automaten. Du erzeugst mithilfe der Teilmengenkonstruktion aus dem nichtdeterministischen endlichen Automaten einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt.

Gibt es diese Möglichkeit bei den Stackautomaten auch? Oder gibt es eine kontextfreie Sprache, die von keinem deterministischen Stackautomaten erkannt wird? Hier ist die Antwort.

Die kontextfreie Sprache $ww^R$

Betrachte einmal die Sprache

$L = \{~ ww^R ~|~ w \in \{a,b\}^* ~\}$

Hierbei bedeutet $w^R$ das Wort $w$ rückwärts gelesen. Die Wörter $ww^R$ der Sprache sind also alle Wörter gerader Länge, die vorwärts und rückwärts gelesen das Gleiche ergeben, wie zum Beispiel abba. Solche Wörter heißen Palindrome.

Diese Sprache wird von der folgenden kontextfreien Grammatik erzeugt:

$G = (V, T, P, S)$ mit

$V = \{S\}$

$T = \{\mathsf{a,b}\}$

$P : ~ S \rightarrow \mathsf aS\mathsf a ~|~ \mathsf bS\mathsf b ~|~ \varepsilon$

$S = S$

 Die Sprache $L$ ist also eine kontextfreie Sprache. Dementsprechend gibt es einen nichtdeterministischen Stackautomaten, der die Sprache erkennt.

Nichtdeterministischer Stackautomat für $ww^R$

Versetze dich in den nichtdeterministischen Stackautomaten hinein, mit dem du ein Wort $ww^R$ erkennst: Du legst die gelesenen Zeichen des Wortes $w$ auf dem Stack ab. Anschließend entfernst du für jedes gelesene Zeichen von $w^R$ die zuvor abgelegten Zeichen von $w$ in umgekehrter Reihenfolge wieder vom Stack. Danach ist der Stack leer und du hast das Wort erkannt.

Für das Wort abba beispielsweise legst du die gelesenen Zeichen a und b auf dem Stack ab und entfernst dann für die weiterhin gelesenen Zeichen b und a die entsprechenden Zeichen wieder vom Stack.

Die Übergangsrelation

Die Übergangsrelation lautet

$\def\arraystretch{1.25} \begin{array}{c}s & e & h & h' & s'\\\hline 0 & \varepsilon & \varepsilon & \$ & 1\\ 1 & \text a & \varepsilon & \text a & 1\\ 1 & \text b & \varepsilon & \text b & 1\\ 1 & \varepsilon & \varepsilon & \varepsilon & 2\\ 2 & \text a & \text a & \varepsilon & 2\\ 2 & \text b & \text b & \varepsilon & 2\\ 2 & \varepsilon & \$ & \varepsilon & 3^* \end{array}$

Mit dem ersten Tupel der Übergangsrelation markierst du zunächst das Ende des Stacks mit dem Stack-Ende-Zeichen $\$$. Du startest im Startzustand $s=0$, liest kein Zeichen des Eingabewortes ($e = \varepsilon$), entfernst kein Zeichen vom Stack ($h = \varepsilon$), legst das Stack-Ende-Zeichen $\$$ auf den Stack ($h' = \$$) und gehst in den Zustand $s'=1$ über.

Mit den beiden nächsten Tupeln legst du die jeweils gelesenen Zeichen auf dem Stack ab. Du liest ein Eingabezeichen ($e=\text a$ oder $e=\text b$), entfernst kein Zeichen vom Stack ($h=\varepsilon$) und legst das gelesene Zeichen auf dem Stack ab ($h'=\text a$ oder $h'=\text b$). Dabei bleibst du die ganze Zeit im Zustand 1.

Mit dem darauf folgenden Tupel schaltest du um: Du gehst in den Zustand 2 über. Ab jetzt entfernst du Zeichen vom Stack.

Mit den beiden weiteren Tupeln entfernst du für jedes gelesene Zeichen das entsprechende Zeichen vom Stack.

Zum Schluss entfernst du das Stack-Ende-Zeichen vom Stack und gehst in den Endzustand 3 über.

Simuliere einmal diesen nichtdeterministischen Stackautomaten auf der Seite https://www.inf.hs-flensburg.de/lang/theor/stackautomat-wwr.htm. So bekommst du ein Gefühl für die Arbeitsweise dieses Stackautomaten.

Nichtdeterminismus

Aber Achtung: Dieser Stackautomat ist hochgradig nichtdeterministisch.

Du musst ahnen, wann du zwischen "auf dem Stack ablegen" und "wieder vom Stack entfernen" umschalten musst. Wann schaltest du um, wenn du das Wort aaaaaa liest? Du weißt ja nicht, wann die Mitte des Wortes erreicht ist. Du kannst dies nur nichtdeterministisch, also sozusagen "schlafwandlerisch" entscheiden.

Beim Nichtdeterminismus ist es entscheidend, dass es eine Abfolge von Zustandsübergängen gibt, mit der das Wort erkannt wird. Nur die Existenz einer solchen Abfolge ist entscheidend.

Zweifellos gibt es eine solche Abfolge von Zustandsübergängen beispielsweise für das Wort aaaaaa.

In ähnlicher Weise gibt es eine Abfolge von Zustandsübergängen für jedes beliebige Wort $ww^R$.

Deterministisch ist das nicht möglich

Einen deterministischen Stackautomaten, der die Sprache $L$ erkennt, gibt es offenbar nicht. Denn der Stackautomat hat keine Möglichkeit, etwa bei dem Wort aaaaaa zu entscheiden, wann er ein a auf dem Stack ablegen und wann er es wieder entfernen muss. Er sieht immer nur das nächste Zeichen des Eingabewortes, er weiß nicht, wann die Mitte des Wortes erreicht ist.

Damit ist klar, dass es kontextfreie Sprachen gibt, die nicht von einem deterministischen Stackautomaten erkannt werden.

Die kontextfreien Sprachen, die von deterministischen Stackautomaten erkannt werden, heißen kurzerhand deterministisch kontextfreie Sprachen (versuche nicht, den Sinn des Begriffs deterministisch kontextfrei naiv zu entschlüsseln - kontextfrei bezieht sich auf eine kontextfreie Grammatik, die die Sprache erzeugt, und deterministisch bezieht sich auf einen deterministischen Stackautomaten, der die Sprache erkennt).

Die deterministisch kontextfreien Sprachen bilden eine echte Teilklasse der kontextfreien Sprachen. Sie sind für Programmiersprachen besonders geeignet.