5.10 Die Grenzen kontextfreier Sprachen

Beispiel Betrachten wir die Sprache \begin{align*} L := \{ a^n b^n c^n \ | \ \ n \geq 0\} \ . \end{align*}

Ein Kellerautomat könnte nun alle \(a\) auf den Stack legen und dann, wenn die \(b\) beginnen, den Stapel abarbeiten. Allerdings hätte er dann, wenn die \(c\) kommen, vergessen, wieviele \(a\) es denn waren. Irgendwie scheinen Kellerautomaten nicht für \(L\) geeignet. Dies ist natürlich nur eine Intuition. Vielleicht kennen wir einfach nicht alle Tricks, die man mit Kellerautomaten (und somit mit kontextfreien Grammatiken) anstellen kann.

Wir werden nun beweisen, dass \(L\) nicht kontextfrei ist; dass es also für \(L\) keine kontextfreie Grammatik gibt. Wir gehen wie folgt vor: wir nehmen eine kontextfreie Grammatik \(G\), die jedes Wort \(\gamma \in L\) ableiten kann. Dann sehen wir uns den Ableitungsbaum für ein "sehr langes" \(\gamma\) an und werden sehen, dass wir in \(G\) andere Wörter \(\gamma'\) ableiten können, die nicht in \(L\) sind. Somit haben wir gezeigt, dass \(G\) keine korrekte Grammatik für \(L\) ist. Als erstes verlangen wir, dass \(G\) in Chomsky-Normalform vorliegt. Dann schauen wir uns für ein \(\gamma = a^n b^n c^n\) den Ableitungsbaum an:

Nun betrachten wir in diesem Ableitungsbaum den längsten Pfad von \(S\) zu einem Nichtterminalknoten, der direkt über den Terminalen steht. Wenn dieser Länge \(d\) hat (also \(d\) Kanten lang ist), dann hat der Baum höchstens \(2^d\) Blätter, also \(|\gamma| \leq 2^d\). Wenn nun \(|\gamma| \geq 2^{|N|} =: p\) ist, dann gibt es einen Pfad der Länge \(|N|\) von diesem \(X\) aufwärts richtung \(S\). Auf diesem liegen \(|N|+1\) Nichtterminalsymbole, mehr als es in \(G\) gibt; also muss ein Terminalsymbol zweimal vorkommen:

Der Pfad vom oberen zum unteren \(Z\) hat höchstens Länge \(N\) (so haben wir diesen Pfad gewählt), und somit hat das Unterwort \(vwx\) höchstens \(p = 2^{|N|}\) Zeichen. Wenn wir nun das Wort \(a^nb^nc^n\) für ein sehr großes \(n\) betrachten, sagen wir \(n \geq p = 2^{|N|}\), dann kann das Wort \(vwx\) nicht alle drei Symbole \(a,b,c\) enthalten; sonst würde es ja alle \(n\) Symbole \(b\) und noch weitere enthalten, wäre also länger als \(n \geq p\); allerdings haben wir ja gesehen, dass \(|vwx| \leq p\) gilt. Nehmen wir nun also der Einfachheit halber an, dass \(vwx\) nicht das Symbol \(c\) enthält: \(vwx \in \{a,b\}^*\) (der andere Fall ist symmetrisch und kann mit den gleichen Argumenten wie unten behandelt werden).

Nun holen wir zum entscheidenden Schlag aus: wir "pumpen" das Wort \(\gamma\) auf, indem wir die Teilbäume mit \(Z\) an der Wurzel wiederholen. Konkret besagt ja oberer Baum, dass \(\gamma\) wie folgt hergeleitet wurde: \begin{align*} S \Step{}^* u Z v \Step{}^* uvZxy \Step{}^* uvwxy \end{align*} Insbesondere heißt das, dass \(Z \Step{}^* vZx\) gilt. Wir können diesen Schritt also wiederholen:

und somit das Wort \(uvvwxxy\) und ganz allgemein jedes Wort \begin{align*} uv^i w x^i y \end{align*} ableiten, für jedes \(i \geq 0\). Selbst für \(i = 0\) geht das:

Betrachten wir nun das Wort \(uwy\). Wir haben ja gesehen, dass in \(uvwxy\) alle \(c\)-Symbole rechts von \(vwx\) liegen, also in \(y\). Das Wort \(uwy\) hat also immer noch \(n\) viele \(c\)-Symbole. Allerdings hat es die Symbole in \(v\) und \(x\) verloren! Wir wissen nicht, wieviele davon \(a\) und \(b\) waren, aber eines ist ganz klar: in \(uwy\) kommen die Symbole \(a,b,c\) nicht mehr gleich häufig vor, und somit \(uwy\not \in L\).

Wir haben also gezeigt, dass die kontextfreie Grammatik \(G\) nicht die Sprache \(L\) erzeugt: wenn wir alle \(\gamma \in L\) erzeugen kann, dann kann sie auch Wörter wie \(uwy \not \in L\) erzeugen. Da unsere Argumentation keine Annahmen über \(G\) getroffen hat, außer, dass sie kontextfrei ist, haben wir gezeigt: \(L\) ist keine kontextfreie Sprache.

Vorsicht! Wir haben angenommen, das \(uwy\) weniger Zeichen hat als \(uvwxy\), weil ja \(v\) und \(x\) fehlen. Kann aber \(v = x = \epsilon\) eintreten? Dies würde unsere Argumentation zerstören. Hier kommt wieder die Chomsky-Normalform zur Hilfe: es gibt keine Produktionen \(X \rightarrow \epsilon\), (außer vielleicht für das Startsymbol \(S\), welches dann aber nicht auf einer rechten Seite auftreten dürfte). Ganz allgemein: wenn eine Grammatik \(G\) in Chomsky-Normalform ein Wort \(\gamma\) herleitet und \(\gamma \ne \epsilon\), dann kommt in der Ableitung keine \(\epsilon\)-Produktion zur Anwendung.

Theorem (Pumping Lemma für kontextfreie Sprachen) Für jede kontextfreie Grammatik \(G\) gibt es eine Zahl \(p \in \N\), so dass jedes Wort \(\gamma \in L(G)\) der Länge \(|\gamma| \geq p\) zerlegt werden kann in \begin{align*} \gamma = uvwxy \ , \end{align*} wobei \(|vwx| \leq p\) gilt und \(v,x\) nicht beide \(\epsilon\) sind, so dass \begin{align*} u v^i w x^i y \in L(G) \end{align*} gilt, für alle \(i \geq 0\). Die Zahl \(p\) kann zum Beispiel als \(2^{N_{\rm CNF}}\) gewählt werden, wobei \(N_{\rm CNF}\) die Anzahl der Nichtterminale in einer zu \(G\) äquivalenten Chomsky-Normalform ist.

Theorem Wenn \(L_1, L_2\) reguläre Sprachen sind, dann sind die folgenden Sprachen auch regulär:

1. \(L_1 \cup L_2\). Das war einfach: wir kombinieren die Grammatiken und fügen die Startproduktionen \(S \rightarrow S_1 \ | \ S_2\) hinzu.
2. \(L_1 \circ L_2\). Das war schon schwieriger, ging aber auch irgendwie.
3. \(L_1^*\). Das ging ähnlich zum vorherigen.
4. \(\bar{L}_1 := \Sigma^* \setminus L_1\), die Komplementsprache. Das ist einfach, sobald man einen endlichen Automaten für \(L_1\) gebaut hat: man tauscht akzeptierende und nicht-akzeptierende Zustände aus.
5. \(L_1^R\), die Sprache, die entsteht, wenn man jedes Wort in \(L_1\) von rechts nach links liest. Dies ist gar nicht so offensichtlich, wenn man reguläre Grammatiken oder endliche Automaten ansieht. Wenn man aber für \(L_1\) einen regulären Ausdruck gebaut hat, wird es zur Trivialität: einfach den Ausdruck umdrehen.
6. \(L_1 \cap L_2\). Hierfür könnte man für \(L_1, L_2\) jeweils endliche Automaten \(M_1, M_2\) bauen und die dann "parallel" laufen lassen; man muss nun sehen, dass man dieses parallele Laufen mit einem Automaten simulieren kann: dieser hat als Zustandsmenge \(Q_1 \times Q_2\), merkt sich also in einem Zustand, in welchen Zuständen \(M_1\) und \(M_2\) sind. Oder man macht es sich einfach:
   • Nach Punkt 4 sind \(\bar{L}_1\) und \(\bar{L}_2\) regulär.
   • Nach Punkt 1 daher auch \(\bar{L}_1 \cup \bar{L}_2\) ist regulär.
   • Nach Punkt 4 ist daher wiederum \(\overline{\bar{L}_1 \cup \bar{L}_2}\) regulär, was nach den De-Morganschen Gesetzen die gleiche Menge ist wie \(L_1 \cap L_2\).

Wie sieht es nun aus, wenn \(L_1, L_2\) kontextfreie Sprachen sind? Welche der obigen Kombinationen sind dann ebenfalls kontextfrei?

Beobachtung Der Schnitt \(L_1 \cap L_2\) zweier kontextfreier Sprachen ist im Allgemeinen nicht kontextfrei. Ein Beispiel ist \begin{align*} L_1 & := \{a^n b^n c^* \ | \ n \geq 0 \}\\ L_2 & := \{a^* b^n c^n \ | \ n \geq 0 \} \end{align*} Diese sind beide kontextfrei (schreiben Sie jeweils eine Grammatik, wenn Sie's nicht glauben). Der Schnitt allerdings ist \begin{align*} L_1 \cap L_2 = \{a^n b^n c^n \ | \ n \geq 0\} \ , \end{align*} genau diejenige Sprache, für die wir oben gezeigt haben, dass sie nicht kontextfrei ist.

Beobachtung Das Komplement \(L\) einer kontextfreien Sprache ist im Allgemeinen nicht kontextfrei. \\ Warum? Wenn er es wäre, dann wäre mit Hilfe von Punkt 1 auch \begin{align*} L_1 \cap L_2 = \overline{ \bar{L}_1 \cup \bar{L_2}} \end{align*} kontextfrei, was es aber im Allgemeinen nicht ist. Befriedigender wäre es allerdings, wenn wir ein konkretes Beispiel hätten.