6.11 Die Grenzen kontextfreier Sprachen

Beispiel 6.11.1 Betrachten wir die Sprache $$\begin{array}{r}L:=\{a^n{b}^n{c}^n|n\ge 0\}.\end{array}$$

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 }^{\prime }$ 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 |\le 2^d$. Wenn nun $|\gamma |\ge 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^n{b}^n{c}^n$ für ein sehr großes $n$ betrachten, sagen wir $n\ge 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\ge p$; allerdings haben wir ja gesehen, dass $|vwx|\le p$ gilt. Nehmen wir nun also der Einfachheit halber an, dass $vwx$ nicht das Symbol $c$ enthält: $vwx\in \{a,b{\}}^{\ast }$ (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{array}{r}S{\stackrel{}{⟹}}^{\ast }uZv{\stackrel{}{⟹}}^{\ast }uvZxy{\stackrel{}{⟹}}^{\ast }uvwxy\end{array}$$ Insbesondere heißt das, dass $Z{\stackrel{}{⟹}}^{\ast }vZx$ gilt. Wir können diesen Schritt also wiederholen:

und somit das Wort $uvvwxxy$ und ganz allgemein jedes Wort $$\begin{array}{r}u{v}^{i}w{x}^{i}y\end{array}$$ ableiten, für jedes $i\ge 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\notin 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\notin 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=ϵ$ eintreten? Dies würde unsere Argumentation zerstören. Hier kommt wieder die Chomsky-Normalform zur Hilfe: es gibt keine Produktionen $X\to ϵ$, (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 ϵ$, dann kommt in der Ableitung keine $ϵ$-Produktion zur Anwendung.

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

Theorem 6.11.3 Wenn $$ reguläre Sprachen sind, dann sind die folgenden Sprachen auch regulär:

1. $$. Das war einfach: wir kombinieren die Grammatiken und fügen die Startproduktionen $$ hinzu.
2. $$. Das war schon schwieriger, ging aber auch irgendwie.
3. $$. Das ging ähnlich zum vorherigen.
4. $$, die Komplementsprache. Das ist einfach, sobald man einen endlichen Automaten für $$ gebaut hat: man tauscht akzeptierende und nicht-akzeptierende Zustände aus.
5. $$, die Sprache, die entsteht, wenn man jedes Wort in $$ 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 $$ einen regulären Ausdruck gebaut hat, wird es zur Trivialität: einfach den Ausdruck umdrehen.
6. $$. Hierfür könnte man für $$ jeweils endliche Automaten $$ 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 $$, merkt sich also in einem Zustand, in welchen Zuständen $$ und $$ sind. Oder man macht es sich einfach:
   • Nach Punkt 4 sind $$ und $$ regulär.
   • Nach Punkt 1 daher auch $$ ist regulär.
   • Nach Punkt 4 ist daher wiederum $$ regulär, was nach den De-Morganschen Gesetzen die gleiche Menge ist wie $$.

Wie sieht es nun aus, wenn $$ kontextfreie Sprachen sind? Welche der obigen Kombinationen sind dann ebenfalls kontextfrei?

Beobachtung 6.11.5 Der Schnitt $$ zweier kontextfreier Sprachen ist im Allgemeinen nicht kontextfrei. Ein Beispiel ist $$ Diese sind beide kontextfrei (schreiben Sie jeweils eine Grammatik, wenn Sie's nicht glauben). Der Schnitt allerdings ist $$ genau diejenige Sprache, für die wir oben gezeigt haben, dass sie nicht kontextfrei ist.

Beobachtung 6.11.6 Das Komplement $$ einer kontextfreien Sprache ist im Allgemeinen nicht kontextfrei. Warum? Wenn er es wäre, dann wäre mit Hilfe von Punkt 1 auch $$ kontextfrei, was es aber im Allgemeinen nicht ist. Befriedigender wäre es allerdings, wenn wir ein konkretes Beispiel hätten.