Formale Sprachen und Automatentheorie – Kontextfreie Sprachen

Bemerkung: Reguläre Sprachen sind nützlich, aber doch sehr begrenzt (sie haben sozusagen ein „endliches“ Gedächtnis). Geht man zur größeren Klasse der Typ-2- oder kontextfreien Sprachen über, so stehen mehr Möglichkeiten offen. Allein schon die Sprache \(L = \{a^n b^n \;|\; n \ge 1\}\) ist eine Typ-2-Sprache, die nicht regulär ist (siehe oben). Weitere Beispiele umfassen Grammatiken für arithmetische Ausdrücke oder Programmiersprachen (die Syntax von praktisch jeder Programmiersprache lässt sich mit einer kontextfreien Grammatik beschreiben).
Eine typische Regel wäre \(\langle \text {Anweisung}\rangle ::= \text {Zuweisung} \;|\; \text {Anweisung}\mathbf {;}\; \text {Anweisung} \;|\;\)
\(\mathbf {if}\; \text {bedingung}\; \mathbf {then}\; \text {Anweisung}\; \mathbf {fi} \;|\; \mathbf {while}\; \text {bedingung}\; \mathbf {do}\; \text {Anweisung}\; \mathbf {od}\) (dabei sind Terminale fett, inklusive dem Semikolon).

Normalformen

Bemerkung: Man will jeder kontextfreien Grammatik eine andere kontextfreie Grammatik zuweisen, die möglichst „einfach“ aufgebaut ist und die gleiche Sprache erzeugt.
Im Folgenden wird dafür angenommen, dass es keine \(\varepsilon \)-Regeln gibt (sonst ersetzt man \(L\) durch \(L \setminus \{\varepsilon \}\)).

Lemma (Beseitigung von Ringableitungen): Sei \(G\) eine Typ-2-Grammatik.
Dann gibt es eine Typ-2-Grammatik \(G’\) mit \(L(G) = L(G’)\), die keine Ringableitungen enthält (d. h. es gibt keine Variablen \(B_1, \dotsc , B_k\) mit \(B_1 \rightarrow \dotsb \rightarrow B_k\) und \(B_k = B_1\)).

Beweis: Ist \(B_1 \rightarrow \dotsb \rightarrow B_k\) mit \(B_k = B_1\) eine Ringableitung, so ersetzt man in den Regeln alle \(B_i\), \(i = 2, \dotsc , k\) durch \(B_1\). Dabei können natürlich Duplikate auftreten (z. B. bei \(A \rightarrow AB_1\) und \(A \rightarrow AB_2\)), diese lässt man weg (Produktionsmenge ist ja eine Menge). Die Regel \(B_1 \rightarrow B_1\) kann man ebenfalls weglassen. Die so entstandene Grammatik \(G’\) erzeugt dieselbe Sprache wie die ursprüngliche Grammatik \(G\).

Lemma (Beseitigung von Regeln der Form \(A \rightarrow B\)): Sei \(G\) eine Typ-2-Grammatik.
Dann gibt es eine Typ-2-Grammatik \(G’\) mit \(L(G) = L(G’)\), die keine Regeln der Form \(A \rightarrow B\) mit \(A\) und \(B\) Variablen enthält.

Beweis: Zunächst lässt sich die Variablenmenge \(V\) ordnen, sodass \(V = \{A_1, \dotsc , A_n\}\) mit \(A_i \not = A_j\) für \(i \not = j\) und \(A_i \rightarrow A_j\) tritt nur für \(i < j\) auf (d. h. \(\forall _{i=1,\dots ,n} \forall _{j=1,\dotsc ,i}\; A_i \rightarrow A_j \notin P\)).

Wieso geht das? Betrachte den gerichteten Graphen mit Knotenmenge \(V = \{C_1, \dotsc , C_n\}\) und Regeln als Kanten (d. h. es gibt eine Kante von \(C_i\) nach \(C_j\) genau dann, falls \(C_i \rightarrow C_j \in P\)). Dieser Graph ist kreisfrei, da oBdA keine Ringableitungen vorhanden sind (siehe Lemma von eben). Nun gibt es ein \(i\), sodass für alle \(j\) gilt, dass \(C_i \rightarrow C_j \notin P\) (andernfalls gäbe es einen Kreis). Man setzt nun \(A_n := C_i\), entfernt \(A_n\) inkl. den eingehenden Kanten aus dem Graphen und wiederholt diese Prozedur. Es kommen also keine Regeln \(A_i \rightarrow A_j \in P\) mit \(i \ge j\) vor (die z. B. im ersten Schritt entfernten Kanten \(A_i \rightarrow A_n\), \(i = 1, \dotsc , n - 1\) sind ja erlaubt).

Nun kann man alle Regeln der Form \(A_i \rightarrow A_j\) eliminieren: Jede Regel \(A_n \rightarrow w\) mit \(w \in (V \cup \Sigma )^+\) hat als rechte Seite \(w \notin V\) keine Variable. Falls es Regeln \(A_i \rightarrow A_n\) mit \(i < n\) gibt, ersetzt man diese Regeln durch \(A_i \rightarrow w\) für jede Regel der Form \(A_n \rightarrow w\). Anschließend gibt es keine Regeln \(A_i \rightarrow A_n\) mit \(i < n\) mehr. Man wiederholt dies mit \(A_{n-1}\) usw. bis \(A_2\).

Die Sprache wird dabei nicht verändert und die so entstandene Grammatik \(G’\) enthält keine Regeln der Form \(A \rightarrow B\) mit \(A\) und \(B\) Variablen.

Chomsky-Normalform: Eine Typ-2-Grammatik heißt in Chomsky-Normalform, falls alle Regeln von der Form \(A \rightarrow BC\) oder \(A \rightarrow a\) sind (\(A, B, C\) Variablen und \(a\) Terminal).

Bemerkung: Die Ableitungsbäume bekommen damit eine sehr regelmäßige Form, denn sie sind alle binär. Jede Ableitung eines Worts der Länge \(n\) hat in einer CNF-Grammatik die Länge von \(2n - 1\) Ableitungsschritten.

Satz (Chomsky-Normalform): Zu jeder kontextfreien Grammatik \(G\) mit \(\varepsilon \notin L(G)\) gibt es eine kontextfreie Grammatik \(G’\) in Chomsky-Normalform mit \(L(G) = L(G’)\).

Beweis: Zunächst führt man für jedes Terminalzeichen eine sog. Pseudovariable ein. Sei also \(\Sigma = \{\sigma _1, \dotsc , \sigma _k\}\). Führe für alle \(i = 1, \dotsc , k\) eine Variable \(V_{\sigma _i}\) ein. Ersetze in allen Regeln Terminale grundsätzlich durch die entsprechenden Pseudoterminale und füge die Regel \(V_{\sigma _i} \rightarrow \sigma _i\) hinzu. Dies verändert die Sprache nicht und alle Regeln haben jetzt die Form von entweder \(A \rightarrow a\) oder \(A \rightarrow w\) mit \(w \in V^+\) und \(|w| \ge 2\) (oBdA nach obigem Lemma).

Die Regeln der Form \(A \rightarrow a\) sind okay (kompatibel zur CNF). Die Regeln \(A \rightarrow B_1 \dotsb B_k\) mit \(k \ge 2\) sind für \(k = 2\) ebenfalls okay, für \(k > 2\) müssen diese umgeformt werden: Diese Regel wird ersetzt durch die Regeln \(A \rightarrow B_1 C_2\), \(C_2 \rightarrow B_2 C_3\) usw. bis \(C_{k-1} \rightarrow B_{k-1} B_k\). Dabei sind \(C_2, \dotsc , C_{k-1}\) neue Variablen. Durch diese Anpassung wird die Sprache ebenfalls nicht geändert, die entstandene Grammatik \(G’\) ist in Chomsky-Normalform.

Bemerkung: Die Vorgehensweise, um eine gegebene kontextfreie Grammatik in ein CNF umzuwandeln, wird aus den konstruktiven Beweisen ersichtlich:

Elimination von Ringableitungen durch Ersetzen aller in der Ringableitung vorkommenden Variablen durch eine einzige Variable
Sortierung der Variablen zu einer Menge \(\{A_1, \dotsc , A_n\}\), sodass keine Regeln \(A_i \rightarrow A_j\) mit \(j \le i\) auftreten
Elimination der Regeln der Form \(A \rightarrow B\) durch Ersetzen von \(A_i \rightarrow A_j\) für \(i = n - 1, \dotsc , 1\)
Pseudoterminale einführen und Ersetzen aller Terminale in den Regeln
Elimination der Regeln mit mehr als zwei Variablen auf der rechten Seite

Greibach-Normalform: Eine Typ-2-Grammatik heißt in Greibach-Normalform, falls alle Regeln von der Form \(A \rightarrow a B_1 \dotsc B_k\) für \(k \ge 0\) sind (\(A, B_i\) Variablen und \(a\) Terminal).

Bemerkung: Mit der Zusatzbedingung \(k \le 1\) erhält man genau die regulären Grammatiken.
(Man kann sogar jede kontextfreie Grammatik in Greibach-Normalform bringen, wobei \(k \le 2\).)

Satz (Greibach-Normalform): Zu jeder kontextfreien Grammatik \(G\) mit \(\varepsilon \notin L(G)\) gibt es eine kontextfreie Grammatik \(G’\) in Greibach-Normalform mit \(L(G) = L(G’)\).

Beweis: Ist \(A\) eine Variable, so werden im Folgenden alle Regeln der Form \(A \rightarrow w\) mit einer beliebigen Satzform \(w\) als \(A\)-Regeln bezeichnet.

Mithilfe folgender Vorüberlegung kann man alle linksrekursiven Regeln entfernen:
Für jede Variable \(A\) teilt man die \(A\)-Regeln in die linksrekursiven Regeln (d. h. \(A \rightarrow A\alpha \) mit beliebigen \(\alpha \)) und die übrigen Regeln (d. h. \(A \rightarrow \beta \), wobei \(\beta \) nicht mit \(A\) beginnt) auf.
Entsprechend dieser Aufteilung seien die \(A\)-Regeln \(A \rightarrow A\alpha _1 \;|\; \dotsb \;|\; A\alpha _k \;|\; \beta _1 \;|\; \dotsb \;|\; \beta _\ell \)
(\(k \ge 0\), \(l \ge 1\)). Diese Regeln kann man ersetzen durch die Regeln
\(A \rightarrow \beta _1 \;|\; \dotsb \;|\; \beta _\ell \), \(A \rightarrow \beta _1 B \;|\; \dotsb \;|\; \beta _\ell B\), \(B \rightarrow \alpha _1 \;|\; \dotsb \;|\; \alpha _k\), \(B \rightarrow \alpha _1 B \;|\; \dotsb \;|\; \alpha _k B\).
Dabei ist \(B\) eine neue Variable. Die erzeugte Sprache wird dadurch nicht verändert.
Dann sind also keine linksrekursiven \(A\)-Regeln mehr vorhanden
(\(\beta \) starten nicht mit \(A\) und \(\alpha \) starten nicht mit \(B\), da \(B\) eine neue Variable ist).

Ohne Einschränkung kann man nach obigem Satz von einer kontextfreien Grammatik in
Chomsky-Normalform ausgehen, wobei die Variablen durchnummeriert sind
(\(V = \{A_1, \dotsc , A_m\}\)).

Der erste Algorithmus formt die Grammatik so um, dass Regeln der Form \(A_i \rightarrow A_j \beta \) nur mit \(i < j\) vorkommen. Dabei müssen ggf. entsprechend der Überlegung wie eben neue Variablen eingeführt werden, um Linksrekursion zu vermeiden.

\begin{align*} &\FOR i := 1 \;\TO m \;\DO \\ &\qquad \FOR j := 1 \;\TO i - 1 \;\DO \\ &\qquad \qquad \FORALL A_i \rightarrow A_j \alpha \in P \;\DO \\ &\qquad \qquad \qquad \IF A_j \rightarrow \beta _1 \;|\; \dotsb \;|\; \beta _n \;\THEN \text {streiche }A_i \rightarrow A_j \alpha ,\; \text {neu in }P\text {: } A_i \rightarrow \beta _1 \alpha \;|\; \dotsb \;|\; \beta _n \alpha \\ &\qquad \qquad \END \\ &\qquad \END \\ &\qquad \FORALL A_i \rightarrow A_i \alpha \in P: \text {beseitige wie in Vorüberlegung}\\ &\END \end{align*} Es werden also die Ableitungsmöglichkeiten \(A_i \Rightarrow A_j \alpha \Rightarrow \beta _k \alpha \) ersetzt durch \(A_i \Rightarrow \beta _k \alpha \).
Nun gibt es zwei Sorten von Regeln: \(A_i \rightarrow A_j \beta \;|\; \alpha _k\) mit \(i < j\) und \(B \rightarrow \beta _k \;|\; \beta _k B\), wobei die \(\alpha _k\) nicht mit einer Variable und die \(\beta _k\) nicht mit \(B\) anfangen.

Der zweite Algorithmus erreicht, dass die rechten Seiten aller \(A_i\)-Regeln mit Terminalen beginnen. Bei den \(A_m\)-Regeln ist dies schon der Fall (Form \(A_m \rightarrow A_j \beta \;|\; \alpha _k\) mit \(j > m\), dies ist aber nicht möglich, daher \(A_m \rightarrow \alpha _k\), wobei die \(\alpha _k\) nicht mit Variablen beginnen).
Die \(A_{m-1}\)-Regeln beginnen entweder mit \(A_m\) oder mit Terminalzeichen. Durch Einsetzen der rechten Seiten aller \(A_m\)-Regeln erhält man auch in allen \(A_{m-1}\)-Regeln rechte Seiten, die mit Terminalen beginnen. So verfährt man induktiv mit \(A_{m-2}\) usw. bis zu \(A_1\).

Nun haben sind alle \(A_i\)-Regeln GNF-konform (die Grammatik war zu Beginn in CNF, d. h. es kommen nur Variablen nach dem beginnenden Terminal). Es gibt nun noch die \(B\)-Regeln, die bei der Entfernung der linksrekursiven Regeln eingeführt wurden. Die rechten Seiten der \(B\)-Regeln beginnen entweder mit \(A_i\) oder mit Terminalen. Da die \(A_i\)-Regeln alle schon mit Terminalen beginnen, kann man einfach einsetzen (analog zu eben). Die so entstandene Grammatik erzeugt die gleiche Sprache und ist in Greibach-Normalform.

Beispiel: Gegeben sei die Grammatik in CNF \(A_1 \rightarrow A_1 A_2 \;|\; A_2 A_3 \;|\; a\), \(A_2 \rightarrow A_3 A_1\), \(A_3 \rightarrow b\).
Beim ersten Algorithmus werden zunächst Regeln der Form \(A_i \rightarrow A_j \beta \) mit \(j \le i\) entfernt. Es ist die linksrekursive Regel \(A_1 \rightarrow A_1 A_2\) vorhanden, die wie in der Vorüberlegung ersetzt wird, sodass die neuen Regeln \(A_1 \rightarrow A_2 A_3 \;|\; a \;|\; A_2 A_3 B \;|\; a B\), \(B \rightarrow A_2 \;|\; A_2 B\),
\(A_2 \rightarrow A_3 A_1\), \(A_3 \rightarrow b\) sind. Für \(A_2\) und \(A_3\) ist nichts zu tun.
Beim zweiten Algorithmus ersetzt man alle \(A_i\)-Regeln, sodass auf den rechten Seiten nur noch Terminale vorkommen, d. h. \(A_1 \rightarrow b A_1 A_3 \;|\; a \;|\; b A_1 A_3 B \;|\; a B\), \(B \rightarrow A_2 \;|\; A_2 B\),
\(A_2 \rightarrow b A_1\), \(A_3 \rightarrow b\). Nun macht man dasselbe für die \(B\)-Regeln:
\(A_1 \rightarrow b A_1 A_3 \;|\; a \;|\; b A_1 A_3 B \;|\; a B\), \(A_2 \rightarrow b A_1\), \(A_3 \rightarrow b\), \(B \rightarrow b A_1 \;|\; b A_1 B\).

Das Pumping-Lemma

Bemerkung: Man kann ein Analogon zum Pumping-Lemma für reguläre Sprachen auch für kontextfreie Sprachen aufstellen. Um die beiden Lemmata zu unterscheiden, nennt man das Pumping-Lemma für reguläre Sprachen auch \(uvw\)-Theorem, während man das Pumping-Lemma für kontextfreie Sprachen \(uvwxy\)-Theorem nennt.

Satz (Pumping-Lemma): Sei \(L \subset \Sigma ^\ast \) eine kontextfreie Sprache.
Dann gilt \(\exists _{n \in \natural } \forall _{z \in L,\; |z| \ge n} \exists _{u, v, w, x, y \in \Sigma ^\ast ,\; uvwxy = z}\; (1. \land 2. \land 3.)\) mit

\(|vx| \ge 1\)
\(|vwx| \le n\)
\(\forall _{i \in \natural _0}\; u v^i w x^i y \in L\)

Beweis: Da die Sprache \(L\) kontextfrei ist, kann man von einer Grammatik \(G = (V, \Sigma , P, S)\) in Chomsky-Normalform ausgehen, wobei \(L = L(G)\).

Wähle \(n = 2^{|V|}\) und sei \(z \in L\) mit \(|z| \ge n\) beliebig. Ein Ableitungsbaum von \(z\) hat folgende Form: Unter der Wurzel \(S\) befindet sich ein Binärbaum (Regeln vom Typ \(A \rightarrow BC\)). Für jedes Kind dieses Binärbaums befindet sich unterhalb vom Binärbaum noch ein weiterer Kindknoten des Ableitungsbaums (Regeln vom Typ \(A \rightarrow a\)). \(z\) kann nun an diesen Kindern abgelesen werden, d. h. der Baum hat \(|z| \ge 2^{|V|}\) viele Kinder. Nach dem Lemma (siehe unten) hat der Ableitungsbaum also mindestens einen Pfad der Länge \(\ge |V|\).

Nun fixiert man einen längsten Pfad im Ableitungsbaum (dieser hat eine Länge \(\ge |V|\)). In diesem Pfad kommen daher \(> |V|\) Variablen vor, es muss sich also mindestens eine Variable wiederholen. Wähle von unten kommend die erste wiederholte Variable, diese sei nun \(A\).
Man teilt nun den Baum und \(z\) folgendermaßen ein: Der Teil unter dem (von unten) ersten Vorkommen von \(A\), der Teil unter dem (von unten) zweiten Vorkommen von \(A\) ohne den ersten Teil sowie der Teil unter \(S\) (also der komplette Baum) ohne die ersten beiden Teile.

\(w\) sei das Wort gebildet aus den Kindern des ersten Teils, \(v\) und \(x\) die Wörter gebildet aus den Kindern des zweiten Teils (durch den ersten Teil zerfallen die Kinder in zwei Abschnitte) sowie \(u\) und \(y\) die Wörter gebildet aus den Kindern des dritten Teils (durch die ersten beiden Teile zerfallen die Kinder in zwei Abschnitte).
Dabei gilt \(|vx| \ge 1\) und \(|vwx| \le n\). Das Erste gilt, da die beiden \(A\)’s nicht identisch sind und das zweite \(A\) mindestens ein Kind hat, in dem sich das erste \(A\) nicht befindet (Regel \(A \rightarrow BC\) wird angewendet). Dieses Kind erzeugt ein nicht-leeres Wort, also ist \(v\) oder \(x\) nicht-leer. Das Zweite gilt, weil der größte Abstand des ersten Vorkommens von \(A\) zu den Blättern \(< |V|\) ist. Es kann also nach dem Lemma (siehe unten) höchstens \(n = 2^{|V|}\) Blätter unter diesem \(A\) geben.

Außerdem gilt anhand des Ableitungsbaums, dass \(S \Rightarrow ^\ast uAy\), \(A \Rightarrow ^\ast vAx\) und \(A \Rightarrow ^\ast w\).
Daher kann man pumpen, d. h. \(S \Rightarrow ^\ast uAy \Rightarrow ^\ast uvAxy \Rightarrow ^\ast uv^2Ax^2y \Rightarrow ^\ast \dotsb \Rightarrow ^\ast uv^iAx^iy \Rightarrow ^\ast uv^iwx^iy\) für \(i \in \natural _0\). Anschaulich „hängt“ man den Baum unter dem zweiten \(A\) (ohne den Baum unter dem ersten \(A\)) so oft wie gewünscht untereinander, bis man mit dem Baum unter dem ersten \(A\) terminiert.

Bemerkung: Für \(u = v = \varepsilon \) erhält man das Pumping-Lemma für reguläre Sprachen.

Bemerkung: Für den Beweis wird das folgende Lemma genutzt.

Binärbaum: Ein Binärbaum ist ein Baum, in dem jeder Knoten, der kein Blatt ist, genau zwei Nachfolger hat.

Lemma (Pfade im Binärbaum): Ein Binärbaum mit mindestens \(2^k\) Blättern hat mindestens einen Pfad der Länge \(\ge k\).

Beweis: Der Beweis erfolgt mittels vollständiger Induktion über \(k \in \natural _0\).

Für \(k = 0\) ist die Behauptung trivial, denn dann hat der Baum mindestens einen Knoten und somit auch einen Pfad der Länge \(0\).

Für \(k \to k + 1\) betrachtet man den linken und den rechten Teilbaum der Wurzel des Baums mit mindestens \(2^{k+1}\) Blättern. Dann hat einer der beiden Teilbäume mindestens \(\frac {2^{k+1}}{2} = 2^k\) Blätter. Nach Induktionsvoraussetzung gibt es in diesem Teilbaum einen Pfad der Länge \(\ge k\). Dieser kann bis zur Wurzel vom „großen“ Baum verlängert werden und liefert einen Pfad der Länge \(\ge k + 1\).

Beispiel: Die Sprache \(L = \{a^n b^n c^n \;|\; n \ge 1\}\) ist nicht kontextfrei. Andernfalls gäbe es nach dem Pumping-Lemma ein \(n \in \natural \) mit obigen Eigenschaften. Wähle \(z = a^n b^n c^n \in L\), es gilt \(|z| = 3n \ge n\). Dann gibt es \(u, v, w, x, y \in \{a, b, c\}^\ast \) mit \(z = uvwxy\) und \(|vx| \ge 1\), \(|vwx| \le n\) und \(\forall _{i \in \natural _0}\; uv^iwx^iy \in L\). Aufgrund \(|vwx| \le n\) kann \(vwx\) nicht \(a\)’s, \(b\)’s und \(c\)’s enthalten (also nicht alle drei Buchstaben auf einmal, sondern höchstens zwei). Daher ist \(uwy \notin L\), denn \(|uwy|_a \not = |uwy|_b\) oder \(|uwy|_b \not = |uwy|_c\), ein Widerspruch zur dritten Eigenschaft.

Beispiel: Die Sprache \(L = \{a^i b^j c^k \;|\; i > j > k,\; k < i - 7\}\) ist nicht kontextfrei. Andernfalls gäbe es nach dem Pumping-Lemma ein \(n \in \natural \) mit obigen Eigenschaften.
Wähle \(z = a^{n+9} b^{n+8} c^{n+1} \in L\), es gilt \(|z| = 3n + 18 \ge n\). Dann gibt es \(u, v, w, x, y \in \{a, b, c\}^\ast \) mit \(z = uvwxy\) und \(|vx| \ge 1\), \(|vwx| \le n\) und \(\forall _{i \in \natural _0}\; uv^iwx^iy \in L\). Es gibt nun drei Fälle:

\(vwx\) enthält \(a\)’s. Dann enthält \(vwx\) keine \(c\)’s (wegen der zweiten Eigenschaft) und es gilt \(uwy \notin L\), falls \(v\) oder \(x\) \(a\)’s enthalten (dann ist \(|uwy|_c = |uvwxy|_c = n + 1\), aber \(n + 1 \not < |uwy|_a - 7 < |uvwxy|_a - 7 = n + 2\)).
Falls \(v\) und \(x\) keine \(a\)’s enthalten, so ist \(vwx = a^r b^s\) mit \(v = \varepsilon \), \(w = a^r b^{s_1}\) und \(x = b^{s - s_1}\). Dann muss \(u = a^t\) sowie \(y = b^{s_2} c^{n+1}\) gelten, wobei \(t + r = n + 9\) und \(s + s_2 = n + 8\).
In diesem Fall ist \(uv^2 wx^2 y = a^{t+r} b^{s_1 + 2(s - s_1) + s_2} c^{n+1} \notin L\), da
\(|uv^2 wx^2 y|_b = s_1 + 2(s - s_1) + s_2 = 2s - s_1 + s_2 = n + 8 + s - s_1 \not < n + 9 = |uv^2 wx^2 y|_a\).
\(vwx\) enthält \(c\)’s. Dann enthält \(vwx\) keine \(a\)’s und es gilt \(uv^9 wx^9 y \notin L\), denn es \(v\) oder \(x\) enthält ein \(b\) oder ein \(c\). Weil aber keine \(a\)’s enthalten sind, gilt \(|uv^9 wx^9 y|_a = |uvwxy|_a = n + 9\), aber \(|uv^9 wx^9 y|_b \ge |uvwxy|_b + 8 = n + 16\) oder \(|uv^9 wx^9 y|_c \ge |uvwxy|_c + 8 = n + 9\).
\(vwx\) enthält weder \(a\)’s noch \(c\)’s. Dann besteht \(vwx\) nur aus \(b\)’s und es gilt \(uv^2 wx^2 y \notin L\), denn \(|uv^2 wx^2 y|_a = |uvwxy|_a = n + 9\), aber \(|uv^2 wx^2 y|_b > |uvwxy|_b = n + 8\).

Beispiel: Dass \(L = \{a^p \;|\; p \text { prim}\}\) nicht kontextfrei ist, kann man wie beim Beweis für die Nicht-Regularität zeigen (siehe oben). Das ist kein Zufall, sondern bei allen Sprachen über einelementigen Alphabeten der Fall: Sei \(L\) kontextfrei und \(z \in L\) mit \(|z| \ge n\). Dann gibt eine Zerlegung \(z = uvwxy\). Aufgrund des einelementigen Alphabets ist \(z = wvxyu = u’v’w’\) mit \(u’ = w\), \(v’ = vx\) und \(w’ = yu\). Es gilt \(|vx| = |v’| \ge 1\), \(|vwx| = |u’v’| \le n\) sowie
\(uv^i wx^i y = u’ (v’)^i w’ \in L\), d. h. man erhält die gleiche Aussage wie beim \(uvw\)-Theorem. Der folgende Satz führt das genauer aus.

Satz (kontextfreie Sprachen über einelementige Alphabete sind regulär):
Sei \(L \subset \Sigma ^\ast \) eine kontextfreie Sprache mit \(|\Sigma | = 1\). Dann ist \(L\) regulär.

Beweis: Sei \(L \subset a^\ast \) eine kontextfreie Sprache. Nach dem Pumping-Lemma für kontextfreie Sprachen gibt es für alle \(z \in L\) mit \(|z| \ge n\) eine Zerlegung \(z = uvwxy = a^{k_1} a^{\ell _1} a^{k_2} a^{\ell _2} a^{k_3} = a^k a^\ell \) mit \(k = k_1 + k_2 + k_3\) und \(\ell = \ell _1 + \ell _2\). Dabei gilt \(\ell > 0\) und \(a^{k + i\ell } \in L\) für alle \(i \in \natural _0\).

Man erhält also für jedes \(z \in L\) mit \(|z| \ge n\) eine Zahl \(\ell \in \{1, \dotsc , n\}\), die Periode von \(z\) genannt wird (die Periode von \(z\) ist evtl. nicht eindeutig).

Sei \(q := n!\), dann gilt \(\ell \;|\; q\) für alle Perioden \(\ell \). Für eine beliebige Zahl \(q’ > q\) wird die Sprache \(L’ := \{x \in L \;|\; |x| < q\} \cup \{a^{r + iq} \;|\; q \le r \le q’,\; a^r \in L,\; i \in \natural _0\}\) definiert.
\(L’\) ist für alle \(q’ > q\) regulär, denn die erste Menge ist endlich und somit regulär. Die zweite Menge ist regulär, da \(\{a^{r + iq} \;|\; i \in \natural _0\}\) für festes \(r, q\) regulär ist (z. B. mit einem entsprechenden DEA) und die zweite Menge eine endliche Vereinigung solcher Mengen ist.
Außerdem gilt \(L’ \subset L\), denn die erste Menge ist eine Teilmenge von \(L\) und bei der zweiten Menge ist \(a^{r + iq} \in L\) für \(a^r \in L\), \(r \ge q\) und \(i \ge 0\), da \(a^r\) die Periode \(\ell \) hat und diese \(q\) teilt.
Falls \(q’\) so gefunden kann, dass \(L \subset L’\) gilt, so gilt \(L = L’\) und der Beweis ist abgeschlossen, da \(L’\) regulär ist.

Wähle zunächst \(q’ = q + 1\). Falls \(L’ = L\), so ist man fertig.
Falls \(L’ \subsetneqq L\), so wähle ein kürzestes Wort \(a^s \in L \setminus L’\). Wird \(q’ > s\) gewählt, so ist \(a^{s + iq} \in L’\) für \(i \in \natural _0\) (ist in der zweiten Menge). Somit sind alle \(a^m\) mit \(m \ge s\) und \(m \equiv s \mod q\) in \(L’\).
Dieser Vorgang wird nun iteriert. Es gibt allerdings höchstens \(q - 1\) Restklassen, sodass die Iteration in endlich vielen Schritten endet.

Abschlusseigenschaften

Satz (Abschlusseigenschaften der kontextfreien Sprachen): Die Klasse der kontextfreien Sprachen ist abgeschlossen unter Vereinigung, Produkt und Stern.

Beweis: Abschluss unter Vereinigung: Seien \(L_1 = L(G_1)\) und \(L_2 = L(G_2)\) kontextfreie Sprachen mit \(G_1 = (V_1, \Sigma , P_1, S_1)\) und \(G_2 = (V_2, \Sigma , P_2, S_2)\), wobei \(V_1 \cap V_2 = \emptyset \) und \(S \notin V_1 \cup V_2\). Dann gilt \(L(G) = L_1 \cup L_2\) mit der kontextfreien Grammatik
\(G = (V_1 \cup V_2 \cup \{S\}, \Sigma , P_1 \cup P_2 \cup \{S \rightarrow S_1 | S_2\}, S)\).
Für „\(\supset \)“ nimmt man z. B. ein Wort \(w \in L_1\). Dann ist \(S_1 \Rightarrow _{G_1}^\ast w\) und es gilt \(S \Rightarrow _G S_1 \Rightarrow _G^\ast w\), da \(P_1\) eine Teilmenge der Regelmenge von \(G\) ist.
Für „\(\subset \)“ sei \(w \in L(G)\), also \(S \Rightarrow _G w\). Da \(S\) in keiner anderen Regel außer \(S \rightarrow S_1 | S_2\) vorkommt, muss z. B. \(S \Rightarrow _G S_1 \Rightarrow _G w\) gelten. Dann gilt allerdings auch \(S_1 \Rightarrow _{G_1}^\ast w\), denn \(S_1\) kann nur nach Variablen in \(V_1\) abgeleitet werden, diese Variablen können auch nur nach Variablen in \(V_1\) abgeleitet werden usw. Daraus folgt dann \(w \in L_1\).

Abschluss unter Produkt: Seien \(G_1\) und \(G_2\) wie eben. Dann gilt \(L(G) = L_1 L_2\) mit der kontextfreien Grammatik \(G = (V_1 \cup V_2 \cup \{S\}, \Sigma , P_1 \cup P_2 \cup \{S \rightarrow S_1 S_2\}, S)\). Der Beweis lässt sich analog durchführen.

Abschluss unter Stern: Sei \(L_1 = L(G_1)\) eine kontextfreie Sprache mit \(G_1 = (V_1, \Sigma , P_1, S_1)\), wobei \(S \notin V_1\) und \(S_1\) oBdA auf keiner rechten Seite vorkommt. Dann gilt \(L(G) = (L_1)^\ast \) mit der kontextfreien Grammatik \(G = (V_1 \cup \{S\}, \Sigma , P, S)\) mit
\(P = (P_1 \setminus \{S_1 \rightarrow \varepsilon \}) \cup \{S \rightarrow \varepsilon | S_1\} \cup \{S_1 \rightarrow S_1 S_1\}\).
Für „\(\supset \)“ sei \(w \in (L_1)^\ast \), d. h. \(w = w_1 \dotsb w_n\) mit \(n \in \natural _0\) und \(w_i \in L_1\). Ist \(n = 0\), so gilt \(S \Rightarrow _G \varepsilon = w\).
Ist \(n \ge 1\), so gilt \(S \Rightarrow _G S_1 \Rightarrow _G S_1 S_1 \Rightarrow _G S_1 S_1 S_1 \Rightarrow _G \dotsb \Rightarrow _G (S_1)^n \Rightarrow _G^\ast w_1 \dotsb w_n = w\).
Für „\(\subset \)“ ist \(w \in L(G)\), d. h. \(S \Rightarrow _G^\ast w\). Der Fall \(w = \varepsilon \) ist trivial. Da \(S_1\) auf keiner rechten Seite in \(P_1\) vorkommt, kann man oBdA \(S \Rightarrow _G S_1 \Rightarrow _G S_1 S_1 \Rightarrow _G S_1 S_1 S_1 \Rightarrow _G \dotsb \Rightarrow _G (S_1)^n \Rightarrow _G^\ast w\) schreiben, indem man die Anwendungen der Regel \(S_1 \rightarrow S_1 S_1\) zuerst vornimmt (die Anzahl dieser Anwendungen sei \(n\)). Es gilt \(S_1 \Rightarrow _{G_1} w_i\) für \(i = 1, \dotsc , n\) und \(w = w_1 \dotsb w_n\). Somit gilt \(w \in (L_1)^\ast \), da \(w_i \in L_1\) für \(i = 1, \dotsc , n\).

Satz (negative Abschlusseigenschaften der kontextfreien Sprachen): Die Klasse der kontextfreien Sprachen ist nicht abgeschlossen unter Schnitt und Komplement.

Beweis: Nicht-Abgeschlossenheit unter Schnitt: Die Sprachen \(L_1 = \{a^i b^j c^j \;|\; i, j \in \natural \}\) und \(L_2 = \{a^i b^i c^j \;|\; i, j \in \natural \}\) sind kontextfrei, wie man leicht prüfen kann (z. B. für \(L_1\) die Grammatik \(S \rightarrow AB\), \(A \rightarrow Aa \;|\; a\), \(B \rightarrow bBc \;|\; bc\)). Der Schnitt ist die Sprache \(L = \{a^i b^i c^i \;|\; i \in \natural \}\). Weiter oben wurde gezeigt, dass \(L\) nicht kontextfrei ist.

Nicht-Abgeschlossenheit unter Komplement: Angenommen, die Klasse der kontextfreien Sprachen wäre abgeschlossen unter Komplement. Seien \(L_1\) und \(L_2\) kontextfreie Sprachen. Dann ist \(L_1 \cap L_2 = \Sigma ^\ast \setminus ((\Sigma ^\ast \setminus L_1) \cup (\Sigma ^\ast \setminus L_2))\). Damit wäre dann auch Abgeschlossenheit unter Schnitt vorhanden, ein Widerspruch.

Der CYK-Algorithmus

Bemerkung: Das Wortproblem ist für Typ-1-Sprachen entscheidbar, d. h. es gibt einen Algorithmus, der zu jedem gegebenen Wort \(w \in \Sigma ^\ast \) und einer Typ-1-Grammatik \(G\) in endlicher Zeit entscheidet, ob \(w \in L(G)\). Der zugehörige Algorithmus hat allerdings exponentielle Zeitkomplexität.
Für den Spezialfall der Typ-2-Sprachen existiert ein optimierter Algorithmus zur Lösung des Wortproblems, der höchstens kubische Zeitkomplexität besitzt, allerdings die Grammatik in Chomsky-Normalform voraussetzt.
Der Algorithmus nennt sich CYK-Algorithmus (Cocke-Younger-Kasami).

Bemerkung: Sei also eine CNF-Grammatik \(G\) und ein Wort \(w \in \Sigma ^\ast \) gegeben. Zur Entscheidung der Frage, ob \(w \in L(G)\) gilt, werden die Fälle \(|w| = 1\) und \(|w| > 1\) unterschieden.
Für \(|w| = 1\) ist \(w \in \Sigma \), also schaut man, ob eine Regel \(S \rightarrow w\) in der Regelmenge \(P\) existiert.
Für \(|w| > 1\) (unter der Annahme, dass \(w \in L(G)\)) gilt \(S \Rightarrow _G AB\) mit \(A \Rightarrow _G^\ast x\), \(B \Rightarrow _G^\ast y\) und \(w = xy\), wobei \(|x|, |y| \ge 1\). Diesen Vorgang kann man für \(x\) und \(y\) wiederholen usw. Bei Wörtern \(x\) der Länge \(|x| = 1\) gilt \(A \Rightarrow ^\ast x\) genau dann, wenn \(A \rightarrow x \in P\).

Allgemein definiert man für ein Wort \(w = w_1 \dotsb w_n \in \Sigma ^\ast \) Mengen \(T_{i,j} \subset V\) mit \(A \in T_{i,j}\) genau dann, wenn \(A \Rightarrow _G^\ast w_i \dotsb w_{i+j-1}\) mit \(j \in \{1, \dotsc , n\}\) und \(i \in \{1, \dotsc , n + 1 - j\}\).
Diese Mengen werden induktiv berechnet (mit steigendem \(j\)). Am Ende entscheidet, ob \(S \in T_{1,n}\). Dies ist der Fall genau dann, wenn \(w \in L(G)\).
Wie berechnet man die Mengen \(T_{i,j}\)? Für \(j = 1\) ist \(T_{i,1} = \{A \in V \;|\; A \rightarrow w_i \in P\}\). Für \(j = 2\) ist \(T_{i,2} = \{A \in V \;|\; \exists _{B, C \in V}\; A \rightarrow BC \in P,\; B \rightarrow w_i \in P,\; C \rightarrow w_{i+1} \in P\}\). Das kann auch umgeschrieben werden zu \(T_{i,2} = \{A \in V \;|\; \exists _{B \in T_{i,1},\; C \in T_{i+1,1}}\; A \rightarrow BC \in P\}\) usw.
Allgemein gilt für \(j \ge 2\), dass \(T_{i,j} = \{A \in V \;|\; \exists _{k \in \{1, \dotsc , j - 1\}} \exists _{B \in T_{i,k},\; C \in T_{i+k,j-k}}\; A \rightarrow BC \in P\}\).

Für \(j \ge 2\) kann man dies auch als Vereinigung
\(T_{i,j} = \bigcup _{k=1}^{j-1} \{A \in V \;|\; \exists _{B \in T_{i,k},\; C \in T_{i+k,j-k}}\; A \rightarrow BC \in P\}\) schreiben. Man berechnet die \(T_{i,j}\) zuerst für \(j = 1\), dann für \(j = 2\) usw. Um \(T_{i,j}\) zu bestimmen, kann man ausnutzen, dass \(T_{r,s}\) für \(s < j\) und beliebige \(r\) schon bekannt ist. Da andere Mengen in der Vereinigung \(T_{i,j}\) nicht vorkommen, kann man so alle \(T_{i,j}\) algorithmisch bestimmen. Genauer organisiert man die Mengen in einer Tabelle:

\[\begin {array}{r|c|c|ccc|c} & w_1 & w_2 & w_3 & \cdots & w_{n-1} & w_n \\\hline \text {Länge } 1 & T_{1,1} & T_{2,1} & T_{3,1} & \cdots & T_{n-1,1} & T_{n,1} \\\hline \text {Länge } 2 & T_{1,2} & T_{2,2} & T_{3,2} & \cdots & T_{n-1,2} & - \\\hline \vdots \\\hline \text {Länge } n - 1 & T_{1,n-1} & T_{2,n-1} & - & \cdots & - & - \\\hline \text {Länge } n & T_{1,n} & - & - & \cdots & - & - \end {array}\]

Dann ist \(w \in L(G)\) äquivalent zu \(S \in T_{1,n}\).

Satz (CYK-Algorithmus): Sei \(G\) eine kontextfreie Grammatik in Chomsky-Normalform. Dann ermittelt folgender Algorithmus für alle \(w = w_1 \dotsb w_n \in \Sigma ^\ast \), dass \(w \in L(G)\) (Wortproblem):

\begin{align*} &\FOR i := 1 \;\TO n \;\DO \\ &\qquad T[i, 1] := \{A \in V \;|\; A \rightarrow w_i \in P\};\\ &\END \\ &\FOR j := 2 \;\TO n \;\DO \\ &\qquad \FOR i := 1 \;\TO n + 1 - j \;\DO \\ &\qquad \qquad T[i, j] := \emptyset ;\\ &\qquad \qquad \FOR k := 1 \;\TO j - 1 \;\DO \\ &\qquad \qquad \qquad T[i, j] := T[i, j] \cup \{A \in V \;|\; \exists _{B \in T[i, k],\; C \in T[i + k, j - k]}\; A \rightarrow BC \in P\};\\ &\qquad \qquad \END \\ &\qquad \END \\ &\END \\ &\IF S \in T[1, n] \;\THEN \text {output}(1) \;\ELSE \text {output}(0); \end{align*} Der Algorithmus hat die bestmögliche Zeitkomplexität \(\O (n^3)\).

Beispiel: Sei die CNF-Grammatik \(G = (\{S, A, B, X, Y\}, \{a, b\}, P, S)\) gegeben mit
\(P = \{S \rightarrow AX \;|\; YB, A \rightarrow XA \;|\; AB \;|\; a, B \rightarrow XY \;|\; BB, X \rightarrow YA \;|\; a, Y \rightarrow XX \;|\; b\}\).
Gilt \(w = aabbaba \in L(G)\)? Der Algorithmus erzeugt folgende Tabelle:

\[\begin {array}{r|c|c|c|c|c|c|c} \text {Länge} & a & a & b & b & a & b & a \\\hline 1 & AX & AX & Y & Y & AX & Y & AX \\\hline 2 & SAY & B & \emptyset & X & B & X & - \\\hline 3 & A & \emptyset & \emptyset & SB & SY & - & - \\\hline 4 & \emptyset & \emptyset & S & Y & - & - & - \\\hline 5 & S & B & \emptyset & - & - & - & - \\\hline 6 & A & \emptyset & - & - & - & - & - \\\hline 7 & S & - & - & - & - & - & - \end {array}\]

(Dabei bedeutet \(V_1 \dotsb V_n\) die Menge \(\{V_1, \dotsc , V_n\} \subset V\).) Also gilt \(w \in L(G)\).

Kellerautomaten

Bemerkung: Das Modell des nicht-deterministischen endlichen Automaten (NEA) soll so erweitert werden, dass auch kontextfreie Sprachen erkannt werden. Dazu muss ein Speicher eingeführt werden, z. B. bei der Sprache \(\{a^n b^n \;|\; n \in \natural \}\) muss \(n\) gespeichert werden, bei \(\{a_1 \dotsb a_n \dollar a_n \dotsb a_1 \;|\; n \in \natural \}\) muss \(a_1 \dotsb a_n\) gespeichert werden usw.

Bemerkung: Einen Kellerautomat stellt man sich als Maschine vor, die aus Eingabeband, Lesekopf, Zustandskontrolle, Keller und Schreib-/Lesekopf für den Keller besteht. In jedem Schritt kann die Zustandskontrolle höchstens ein Zeichen lesen, der Lesekopf bewegt sich dabei unwiderruflich nach vorne. Gleichzeitig ist das letzte dem Keller hinzugefügte Element sichtbar, bei Bedarf kann mehr Information auf dem Keller gespeichert oder auch bestehende Information des Kellers gelöscht werden. Der Keller ist dabei ein Pushdown-Stack, d. h. die Informationen sind nach ihrem Ablegen absteigend sortiert.

nicht-deterministischer Kellerautomat (PDA):
Ein nicht-deterministischer Kellerautomat oder PDA (pushdown automaton) ist ein \(6\)-Tupel \(M = (Z, \Sigma , \Gamma , \delta , z_0, \#)\), wobei

\(Z\) eine endliche, nicht-leere Menge (die Menge der Zustände),
\(\Sigma \) eine endliche, nicht-leere Menge mit \(Z \cap \Sigma = \emptyset \) (das Eingabealphabet),
\(\Gamma \) eine endliche, nicht-leere Menge mit \(Z \cap \Gamma = \emptyset \) (das Kelleralphabet),
\(\delta \colon Z \times (\Sigma \cup \{\varepsilon \}) \times \Gamma \rightarrow \P _E(Z \times \Gamma ^\ast )\) (die Überführungsfunktion),
\(z_0 \in Z\) (der Startzustand) und
\(\# \in \Gamma \) (das unterste Kellersymbol) ist.

Dabei ist \(\P _E(A) := \{B \subset A \;|\; B \text { endlich}\}\).

Bemerkung: Es gibt zwei Arten von Übergängen:
Bei normalen Übergängen \((q, B_1 \dotsb B_k) \in \delta (p, a, A)\) wird der Buchstabe \(a\) vom Eingabeband gelesen und der Lesekopf um eins weitergerückt. Gleichzeitig wird der oberste Kellerbuchstabe \(A\) vom Keller gelöscht und durch \(B_1 \dotsb B_k\) mit \(k \in \natural _0\) ersetzt.
Bei \(\varepsilon \)-Übergängen \((q, B_1 \dotsb B_k) \in \delta (p, \varepsilon , A)\) läuft alles analog, außer dass kein Eingabebuchstabe gelesen wird (d. h. die Position des Lesekopfs bleibt unverändert).

Konfiguration:
Eine Konfiguration \(k\) des PDA \(M = (Z, \Sigma , \Gamma , \delta , z_0, \#)\) ist ein Element \(k \in Z \times \Sigma ^\ast \times \Gamma ^\ast \).

Übergangsrelation: Auf der Menge \(Z \times \Sigma ^\ast \times \Gamma ^\ast \) wird eine Relation \(\vdash \) definiert durch
\((z, a_1 a_2 \dotsb a_n, A_1 A_2 \dotsb A_m) \vdash (z’, a_2 \dotsb a_n, B_1 \dotsb B_k A_2 \dotsb A_m)\) für \((z’, B_1 \dotsb B_k) \in \delta (z, a_1, A_1)\) bzw. \((z, a_1 \dotsb a_n, A_1 A_2 \dotsb A_m) \vdash (z’, a_1 \dotsb a_n, B_1 \dotsb B_k A_2 \dotsb A_m)\) für \((z’, B_1 \dotsb B_k) \in \delta (z, \varepsilon , A_1)\) mit \(n \in \natural \) bzw. \(n \in \natural _0\), \(m \in \natural \) und \(k \in \natural _0\) (Übergangsrelation).
\(\vdash ^\ast \) ist der reflexive und transitive Abschluss von \(\vdash \).

akzeptierte Sprache: Die von einem PDA \(M = (Z, \Sigma , \Gamma , \delta , z_0, \#)\) akzeptierte Sprache ist \(N(M) := \{x \in \Sigma ^\ast \;|\; \exists _{z \in Z}\; (z_0, x, \#) \vdash ^\ast (z, \varepsilon , \varepsilon )\}\).

Bemerkung: Diese Version der Definition heißt akzeptierte Sprache durch leeren Keller, es gibt auch Akzeptierung durch Endzustand. Wenn der Keller leer ist, endet die Berechnung in jedem Fall, denn für leeres Eingabeband ist die Berechnung erfolgreich, andernfalls ist sie nicht erfolgreich (für jeden Übergang wird ein Kellerzeichen benötigt).

Beispiel: Gesucht wird ein PDA für markierte Palindrome, d. h. für
\(L = \{a_1 \dotsb a_n \dollar a_n \dotsb a_1 \;|\; n \in \natural \}\). Man definiert \(M = (\{z_0, z_1\}, \{a, b, \dollar \}, \{\#, A, B\}, \delta , z_0, \#)\) und die Kurzschreibweise \(zaA \rightarrow z’x\) für \((z’, x) \in \delta (z, a, A)\). Dann setzt man
\(z_0 a \# \rightarrow z_0 A \#\), \(z_0 a A \rightarrow z_0 A A\), \(z_0 a B \rightarrow z_0 A B\) und analog
\(z_0 b \# \rightarrow z_0 B \#\), \(z_0 b A \rightarrow z_0 B A\), \(z_0 b B \rightarrow z_0 B B\). Außerdem ist
\(z_0 \dollar \# \rightarrow z_1 \#\), \(z_0 \dollar A \rightarrow z_1 A\), \(z_0 \dollar B \rightarrow z_1 B\) sowie \(z_1 a A \rightarrow z_1 \varepsilon \), \(z_1 b B \rightarrow z_1 \varepsilon \), \(z_1 \varepsilon \# \rightarrow z_1 \varepsilon \).
Um zu zeigen, dass \(N(M) = L\) gilt, zeigt man zunächst \(w \dollar w^R \in N(M)\) für alle \(w \in \{a, b\}^\ast \), d. h. \((z_0, w \dollar w^R, \#) \vdash ^\ast (z_i, \varepsilon , \varepsilon )\) für ein \(i \in \{0, 1\}\) (dabei ist \(w^R := w_n \dotsb w_1\) für \(w = w_1 \dotsb w_n\)).
Ein möglicher Zwischenschritt ist dabei die stärkere Behauptung
\(\forall _{w \in \{a, b\}^+}\; (z_0, w \dollar w^R, \#) \vdash ^\ast (z_0, \dollar w^R, \widehat {w}^R \#) \vdash (z_1, w^R, \widehat {w}^R \#) \vdash ^\ast (z_1, \varepsilon , \varepsilon )\) mit \(\widehat {w} = \widehat {w}_1 \dotsb \widehat {w}_n\) und \(\widehat {a} = A\), \(\widehat {b} = B\) für \(w = w_1 \dotsb w_n\). Die erste Relation \(\vdash ^\ast \) lässt sich durch Induktion zeigen (\((z_0, v \dollar w^R, y) \vdash ^\ast (z_0, \dollar w^R, \widehat {v}^R y)\) für \(v \in \{a, b\}^\ast \) beliebig). Analog zeigt man die andere Richtung
\(\forall _{x \in \{a, b\}^\ast }\; (\exists _{i \in \{0, 1\}}\; (z_0, x, \#) \vdash ^\ast (z_i, \varepsilon , \varepsilon )) \;\Rightarrow \; (\exists _{w \in \{a, b\}^\ast }\; x = w \dollar w^R)\) (zunächst stellt man fest, dass nur \(i = 1\) möglich ist, da von \(z_0\) aus \(\#\) nicht entfernt wird, danach verfährt man ähnlich wie eben).

Satz (PDA charakterisieren die kontextfreien Sprachen):
Eine Sprache \(L\) ist genau dann kontextfrei, wenn sie von einem PDA erkannt wird.

Beweis: Zunächst sei eine kontextfreie Grammatik \(G = (V, \Sigma , P, S)\) gegeben. Gesucht ist also ein PDA \(M\) mit \(N(M) = L(G)\). Dazu wählt man \(M = (\{z\}, \Sigma , V \cup \Sigma , \delta , z, S)\) und \(\delta \) gegeben durch \((z, \alpha ) \in \delta (z, \varepsilon , X)\) für alle Regeln \(X \rightarrow \alpha \in P\) und \((z, \varepsilon ) \in \delta (z, a, a)\) für alle Terminale \(a \in \Sigma \). Anschaulich wird also \(X\) auf dem Keller durch \(\alpha \) ersetzt bzw. passende Terminale, die ganz oben auf dem Keller (also ganz am Anfang der Ableitung) liegen, einfach weggelesen. Der Kellerinhalt symbolisiert die momentane Ableitung von oben nach unten. Man kann zeigen, dass \(N(M) = L(G)\) gilt.

Nun sei ein PDA \(M = (Z, \Sigma , \Gamma , \delta , z_0, \#)\) gegeben. Gesucht ist eine Typ-2-Grammatik \(G\) mit \(N(M) = L(G)\). OBdA vergrößere \(M\) den Keller bei jedem Übergang um maximal ein Symbol. Dies kann man immer erreichen, indem man andernfalls mehr Zustände einführt, die per \(\varepsilon \)-Übergänge wie in einer Kette miteinander verbunden sind. Die Grammatik \(G\) sei definiert durch \(G = (V, \Sigma , P, S)\) mit \(V = \{S\} \cup (Z \times \Gamma \times Z)\). Anschaulich bedeutet die Variable \((z_1, A, z_2)\), dass man im Zustand \(z_1\) mit dem obersten Kellersymbol \(A\) startet und das Ziel hat, im Zustand \(z_2\) zu sein, wenn \(A\) aus dem Keller erstmals entfernt wird. In der Grammatik werden \(\varepsilon \)-Regeln erlaubt (diese kann man oBdA in eine Grammatik ohne \(\varepsilon \)-Regeln umformen). Dann befinden sich für \(a \in \Sigma \cup \{\varepsilon \}\) und \(z \in Z\) die Regeln \(S \rightarrow (z_0, \#, z)\), \((z, A, z’) \rightarrow a\) (falls \((z’, \varepsilon ) \in \delta (z, a, A)\)), \((z, A, z’) \rightarrow a (z_1, B, z’)\) (falls \((z_1, B) \in \delta (z, a, A)\)) und \((z, A, z’) \rightarrow a (z_1, B, z_2) (z_2, C, z’)\) (falls \((z_1, BC) \in \delta (z, a, A)\)) in \(P\). Man kann zeigen, dass \(N(M) = L(G)\) gilt.

Bemerkung: Im Beweis sieht man: Jede kontextfreie Sprache kann von einem PDA erkannt werden, der nur einen einzigen Zustand besitzt. Zu jeder kontextfreien Sprache (z. B. in Greibach-Normalform gegeben) gibt es einen PDA, der in Echtzeit arbeitet, d. h. in jedem Schritt wird ein Zeichen eingelesen.

Deterministisch kontextfreie Sprachen

Bemerkung: Für viele Anwendungen sind die kontextfreien Sprachen zu allgemein, während die regulären Sprachen zu speziell sind. Man führt daher eine echte Teilmenge bzw. Obermenge der kontextfreien bzw. regulären Sprachen ein.

deterministischer Kellerautomat (DPDA):
Ein deterministischer Kellerautomat oder DPDA (deterministic pushdown automaton) ist ein PDA \(M = (Z, \Sigma , \Gamma , \delta , z_0, \#)\) mit einer Endzustandsmenge \(E \subset Z\), sodass
\(\forall _{z \in Z} \forall _{a \in \Sigma } \forall _{A \in \Gamma }\; |\delta (z, a, A)| + |\delta (z, \varepsilon , A)| \le 1\). DPDAs akzeptieren durch Endzustand und nicht durch leeren Keller, d. h. \(N(M) := \{x \in \Sigma ^\ast \;|\; \exists _{z \in E} \exists _{W \in \Gamma ^\ast }\; (z_0, x, \#) \vdash ^\ast (z, \varepsilon , W)\}\).

Beispiel: Anschaulich gibt es in jeder Konfiguration \(k \in Z \times \Sigma ^\ast \times \Gamma ^\ast \) höchstens eine Folgekonfiguration \(k’ \in Z \times \Sigma ^\ast \times \Gamma ^\ast \) mit \(k \vdash k’\). Für PDAs ist Akzeptierung durch Endzustand und leeren Keller äquivalent. Für DPDAs gilt dies nicht mehr, denn ist nach dem Lesen eines Wortes \(w \in \Sigma ^\ast \) durch den DPDA der Keller leer, so gibt es kein Wort \(ww’\) mit \(w’ \in \Sigma ^+\), das ebenfalls akzeptiert werden würde, denn nach dem Lesen von \(w\) befindet sich der Automat immer in demselben Zustand.

\(\CFL \):
Die Menge \(\CFL := \{L \subset \Sigma ^\ast \;|\; \exists _{\text {PDA } M}\; N(M) = L\}\) ist die Menge aller kontextfreien Sprachen.

\(\DCFL \): Die Menge \(\DCFL := \{L \subset \Sigma ^\ast \;|\; \exists _{\text {DPDA } M}\; N(M) = L\}\) ist die Menge aller
deterministisch kontextfreien Sprachen.

Beispiel: Beispiele für deterministisch kontextfreie Sprachen sind die markierten Palindrome \(\{w \dollar w^R \;|\; w \in \Sigma ^\ast \}\), \(\{a^n b^n \;|\; n \in \natural \}\), \(L_1 = \{a^n b^n c^m \;|\; m, n \in \natural \}\), \(L_2 = \{a^m b^n c^n \;|\; m, n \in \natural \}\) und \(\{a^n b^m c^n \;|\; m, n \in \natural \}\).

Satz (Abschlusseigenschaften von \(\DCFL \)):
\(\DCFL \) ist abgeschlossen unter Komplement, aber nicht unter Durchschnitt und Vereinigung.

Beweis: Für das Komplement komplementiert man die Endzustandsmenge des DPDAs. Dies genügt allerdings noch nicht: Befindet sich der DPDA nach dem Lesen von \(w\) in einem Zustand in \(Z \setminus E\), heißt das noch nicht, dass \(w \notin N(M)\) gilt, denn man könnte noch durch \(\varepsilon \)-Übergänge in einen Endzustand wechseln. Das entstehende Problem ist nicht-trivial, kann aber bewiesen werden.

Die Sprachen \(L_1\) und \(L_2\) aus obigem Beispiel sind in \(\DCFL \), aber der Schnitt \(L_1 \cap L_2\) ist nicht einmal in \(\CFL \), also auch nicht in \(\DCFL \).

Die Nicht-Abgeschlossenheit unter Vereinigung ergibt sich aus den Regeln von de Morgan.

Bemerkung: \(\DCFL \) ist aufgrund der unterschiedlichen Abschlusseigenschaften echt in \(\CFL \) enthalten. Außerdem ist \(\DCFL \) eine echte Obermenge von \(\REG \), denn auch hier unterscheiden sich die Abschlusseigenschaften (alternativ sucht man entsprechende Sprachen).

Satz (Abschlusseigenschaften von \(\DCFL \) und \(\CFL \) mit \(\REG \)):
Aus \(L \in \DCFL \) und \(L’ \in \REG \) folgt \(L \cap L’ \in \DCFL \).
Aus \(L \in \CFL \) und \(L’ \in \REG \) folgt \(L \cap L’ \in \CFL \).

Beweis: Für beide Aussagen wählt man Akzeptierung durch Endzustand und kombiniert den jeweiligen (D)PDA für \(L\) mit dem DEA für \(L’\) (Kreuzprodukt). Endzustände des kombinierten (D)PDA sind die Paare, bei denen beiden Komponenten (im (D)PDA und im DEA) Endzustände sind.

Entscheidbarkeit bei kontextfreien Sprachen

Satz (Entscheidbarkeit bei kontextfreien Sprachen): Das Wortproblem, das Leerheitsproblem und das Endlichkeitsproblem sind für kontextfreie Sprachen entscheidbar.

Beweis: Das Wortproblem ist sogar effizient entscheidbar (durch CYK-Algorithmus bei Grammatik in CNF).

Das Leerheitsproblem ist z. B. mit dem Pumping-Lemma für kontextfreie Sprachen \(L\) lösbar. Man wählt die Zahl \(n\) aus dem Pumping-Lemma (Anzahl der Variablen der Grammatik) und prüft alle Wörter der Länge \(< n\) auf Mitgliedschaft in \(L\). Dies sind endlich viele, d. h. man kann dies mit einem Algorithmus entscheiden. Falls es ein solches gibt, so ist \(L \not = \emptyset \). Umgekehrt folgt aus \(L \not = \emptyset \), dass es ein Wort der Länge \(< n\) in \(L\) gibt (ein Wort in \(L\) der Länge \(\ge n\) kann man negativ pumpen und erhält ein kürzeres Wort in \(L\)).
Alternativ kann man einen Markierungsalgorithmus entwickeln, der die Menge der produktiven Variablen (die Variablen, die in ein Terminalwort abgeleitet werden können) findet (hier ist die Frage, ob \(S\) produktiv ist).

Die Endlichkeit geht auch mit dem Pumping-Lemma und analog zu den regulären Sprachen (gibt es kein \(w \in L\) mit \(n \le |w| < 2n\)?).

Satz (Entscheidbarkeit bei deterministisch kontextfreien Sprachen): Das Problem „Gleichheit mit regulären Sprachen“ ist für deterministisch kontextfreie Sprachen entscheidbar, d. h. für \(L_1 \in \DCFL \) und \(L_2 \in \REG \) ist die Frage, ob \(L_1 = L_2\) gilt, entscheidbar.

Beweis: Es gilt \(L_1 = L_2\) genau dann, wenn \(L_1 \subset L_2\) und \(L_2 \subset L_1\). Dies kann man umschreiben zu \(L_1 \setminus L_2 = \emptyset \) und \(L_2 \setminus L_1 = \emptyset \).
Mit Komplementen dargestellt ist dies äquivalent zu \(L_1 \cap (\Sigma ^\ast \setminus L_2) = \emptyset \) und \(L_2 \cap (\Sigma ^\ast \setminus L_1) = \emptyset \). Da \(L_1 \cap (\Sigma ^\ast \setminus L_2)\) und \(L_2 \cap (\Sigma ^\ast \setminus L_1)\) aufgrund der Abschlusseigenschaften in \(\DCFL \) sind, ist das Gleichheitsproblem mit dem Leerheitsproblem entscheidbar.