Lektion 2.4

Kontextfreie Grammatiken und Ableitungsbäume

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • kontextfreie Grammatiken lesen und für einfache Sprachen selbst aufstellen,

  • Ableitungsbäume, Links- und Rechtsableitungen zu einem Wort angeben,

  • Mehrdeutigkeit erkennen und an einer Ausdrucksgrammatik mit Vorrang beheben,

  • eine Grammatik in Chomsky-Normalform bringen und mit dem CYK-Algorithmus in O(n3)O(n^3) entscheiden, ob ein Wort dazugehört,

  • mit dem Pumping-Lemma für kontextfreie Sprachen zeigen, dass {anbncn}\{a^n b^n c^n\} nicht kontextfrei ist.

Vorausgesetzt: Grammatiken und die Chomsky-Hierarchie, Grenzen endlicher Automaten: das Pumping-Lemma

Ein Compiler liest den Text a + a * a und muss entscheiden, ob er zuerst addiert oder zuerst multipliziert. Dazu reicht es nicht zu wissen, ob der Text ein erlaubter Ausdruck ist; der Compiler braucht seine Struktur: welche Teile zusammengehören. Dazu kommen Klammern, die beliebig tief geschachtelt sein dürfen.

Mit endlichen Automaten geht das nicht. Schon die Sprache {anbn:n≥0}\{a^n b^n : n \ge 0\}, ein Modell für „gleich viele öffnende wie schließende Klammern“, ist nicht regulär, wie das Pumping-Lemma zeigt. Kontextfreie Grammatiken sind das Werkzeug, mit dem Programmiersprachen tatsächlich beschrieben werden. Sie erzeugen solche Sprachen und liefern zu jedem Wort einen Baum, der seine Struktur zeigt.

Vermute zuerst

Eine Grammatik hat die Variable SS und die beiden Regeln S→aSbS \to aSb und S→εS \to \varepsilon. Man beginnt mit SS und ersetzt so lange ein SS durch eine rechte Seite, bis keine Variable mehr übrig ist. Welche Wörter entstehen?

Definition

Kontextfreie Grammatik

Eine kontextfreie Grammatik ist ein Tupel G=(V,Σ,P,S)G = (V, \Sigma, P, S) mit einer endlichen Menge VV von Variablen, einem Alphabet Σ\Sigma von Terminalen (V∩Σ=∅V \cap \Sigma = \emptyset), einem Startsymbol S∈VS \in V und einer endlichen Menge PP von Regeln der Form A→αA \to \alpha mit A∈VA \in V und α∈(V∪Σ)∗\alpha \in (V \cup \Sigma)^*.

„Kontextfrei“ heißt: Links steht genau eine Variable, und sie darf ersetzt werden, egal was links und rechts von ihr steht. Ein Ableitungsschritt βAγ⇒βαγ\beta A \gamma \Rightarrow \beta \alpha \gamma ersetzt ein Vorkommen von AA nach einer Regel A→αA \to \alpha; ⇒∗\Rightarrow^* heißt „in null oder mehr Schritten“. Jedes Wort aus (V∪Σ)∗(V \cup \Sigma)^* mit S⇒∗βS \Rightarrow^* \beta heißt Satzform. Die erzeugte Sprache ist L(G)={w∈Σ∗:S⇒∗w}L(G) = \{w \in \Sigma^* : S \Rightarrow^* w\}. Mehrere Regeln mit derselben linken Seite fasst man mit ∣\mid zusammen: S→aSb∣εS \to aSb \mid \varepsilon.

Wir schreiben Variablen groß und Terminale klein.

Beispiel

Klammerwörter und ein Gegenbeispiel

Liest man a als öffnende und b als schließende Klammer, erzeugt GDG_D mit den Regeln S→aSb∣SS∣εS \to aSb \mid SS \mid \varepsilon genau die korrekt geschachtelten Klammerwörter. Eine Ableitung von abababab:

S⇒SS⇒aSbS⇒abS⇒abaSb⇒ababS \Rightarrow SS \Rightarrow aSbS \Rightarrow abS \Rightarrow abaSb \Rightarrow abab

Die Palindrome über {a,b}\{a, b\} erzeugt S→aSa∣bSb∣a∣b∣εS \to aSa \mid bSb \mid a \mid b \mid \varepsilon. Gegenbeispiel: Eine Regel wie aB→abaB \to ab ist nicht kontextfrei, denn links steht nicht eine einzelne Variable: BB darf hier nur ersetzt werden, wenn links davon ein a steht.

Definition

Ableitungsbaum

Ein Ableitungsbaum zu GG ist ein geordneter Baum mit diesen Eigenschaften:

  • Die Wurzel ist mit SS beschriftet, jeder innere Knoten mit einer Variablen.
  • Hat ein innerer Knoten AA die Kinder X1,…,XkX_1, \dots, X_k (von links nach rechts), dann ist A→X1⋯XkA \to X_1 \cdots X_k eine Regel; für A→εA \to \varepsilon hat er ein einziges Kind ε\varepsilon.
  • Die Blätter sind Terminale oder ε\varepsilon. Von links nach rechts gelesen ergeben sie das erzeugte Wort.

Bäume schreiben wir hier in Klammerform: A[… ]A[\dots] ist ein Knoten AA mit den Kindern in der Klammer. Der Baum zu aabbaabb in S→aSb∣εS \to aSb \mid \varepsilon ist S[ a  S[ a  S[ε]  b ]  b ]S[\,a\; S[\,a\; S[\varepsilon]\; b\,]\; b\,].

Definition

Links- und Rechtsableitung

Ein Baum legt fest, welche Regeln wo angewandt werden, aber nicht, in welcher Reihenfolge. Bei einer Linksableitung wird in jedem Schritt die am weitesten links stehende Variable ersetzt, bei einer Rechtsableitung die am weitesten rechts stehende. Zu jedem Ableitungsbaum gibt es genau eine Linksableitung und genau eine Rechtsableitung.

Beispiel mit der Ausdrucksgrammatik E→E+T∣TE \to E + T \mid T, T→T∗F∣FT \to T * F \mid F, F→(E)∣aF \to (E) \mid a und dem Wort a+a∗aa + a * a:

SchrittLinksableitungRechtsableitung
1E+TE + TE+TE + T
2T+TT + TE+T∗FE + T * F
3F+TF + TE+T∗aE + T * a
4a+Ta + TE+F∗aE + F * a
5a+T∗Fa + T * FE+a∗aE + a * a
6a+F∗Fa + F * FT+a∗aT + a * a
7a+a∗Fa + a * FF+a∗aF + a * a
8a+a∗aa + a * aa+a∗aa + a * a

Beide gehören zu demselben Baum E[ E[T[F[a]]]  +  T[ T[F[a]]  ∗  F[a] ] ]E[\,E[T[F[a]]]\; +\; T[\,T[F[a]]\; *\; F[a]\,]\,].

Kurz geprüft

In der Linksableitung oben steht nach Schritt 4 die Satzform a+Ta + T. Welche Satzform kommt in einer Linksableitung nach a+T∗Fa + T * F?

Definition

Mehrdeutigkeit

Eine Grammatik heißt mehrdeutig, wenn es ein Wort mit zwei verschiedenen Ableitungsbäumen gibt, gleichwertig: mit zwei verschiedenen Linksableitungen. Die einfache Ausdrucksgrammatik E→E+E∣E∗E∣(E)∣aE \to E + E \mid E * E \mid (E) \mid a ist mehrdeutig:

BaumLinksableitungBedeutung
1E[ E[a]+E[ E[a]∗E[a] ] ]E[\,E[a] + E[\,E[a] * E[a]\,]\,]E⇒E+E⇒a+E⇒a+E∗E⇒a+a∗E⇒a+a∗aE \Rightarrow E + E \Rightarrow a + E \Rightarrow a + E * E \Rightarrow a + a * E \Rightarrow a + a * aa+(a∗a)a + (a * a)
2E[ E[ E[a]+E[a] ]∗E[a] ]E[\,E[\,E[a] + E[a]\,] * E[a]\,]E⇒E∗E⇒E+E∗E⇒a+E∗E⇒a+a∗E⇒a+a∗aE \Rightarrow E * E \Rightarrow E + E * E \Rightarrow a + E * E \Rightarrow a + a * E \Rightarrow a + a * a(a+a)∗a(a + a) * a

Für einen Compiler ist das fatal: Mit a=2a = 2 ergibt der erste Baum 66, der zweite 88.

Beispiel

Vorrang in die Grammatik einbauen

Die Grammatik E→E+T∣TE \to E + T \mid T, T→T∗F∣FT \to T * F \mid F, F→(E)∣aF \to (E) \mid a von oben erzeugt dieselben Ausdrücke, ist aber eindeutig. Jede Variable steht für eine Vorrangstufe: EE für Summen, TT (Term) für Produkte, FF (Faktor) für ein a oder einen geklammerten Ausdruck. Ein ++ kann nur durch E→E+TE \to E + T entstehen; ein ∗* unterhalb davon gehört deshalb zu einem TT und bindet stärker.

Dass E→E+TE \to E + T links rekursiv ist (EE steht links in der rechten Seite), macht ++ linksassoziativ: a+a+aa + a + a hat nur den Baum, der (a+a)+a(a + a) + a entspricht. Mehrdeutigkeit ist eine Eigenschaft der Grammatik, nicht der Sprache. Es gibt aber auch kontextfreie Sprachen, die nur mehrdeutige Grammatiken haben, etwa {aibjck:i=j oder j=k}\{a^i b^j c^k : i = j \text{ oder } j = k\}; man nennt sie inhärent mehrdeutig.

Häufige Fehler

Zwei Ableitungen heißt nicht mehrdeutig

„Das Wort a+a∗aa + a * a hat in der Vorranggrammatik eine Linksableitung und eine davon verschiedene Rechtsableitung, also ist die Grammatik mehrdeutig.“

Richtig ist

Fast jedes Wort hat viele Ableitungen, die sich nur in der Reihenfolge der Schritte unterscheiden. Mehrdeutig ist eine Grammatik erst, wenn ein Wort zwei verschiedene Bäume hat. Vergleiche deshalb nur Ableitungen derselben Art, zum Beispiel zwei Linksableitungen.

Satz

Chomsky-Normalform

Eine kontextfreie Grammatik ist in Chomsky-Normalform (CNF), wenn jede Regel die Form A→BCA \to BC oder A→aA \to a hat (A,B,C∈VA, B, C \in V, a∈Σa \in \Sigma). Zusätzlich ist S→εS \to \varepsilon erlaubt, wenn SS auf keiner rechten Seite vorkommt.

Zu jeder kontextfreien Grammatik gibt es eine Grammatik in Chomsky-Normalform, die dieselbe Sprache erzeugt.

Schritt für Schritt

Klammerwörter in Chomsky-Normalform

Ausgangspunkt ist GDG_D: S→aSb∣SS∣εS \to aSb \mid SS \mid \varepsilon.

  1. Neues Startsymbol, weil SS rechts vorkommt:

    S0→S,S→aSb∣SS∣εS_0 \to S, \qquad S \to aSb \mid SS \mid \varepsilon
Schritt 1 von 5
Definition

CYK-Algorithmus

Der Algorithmus von Cocke, Younger und Kasami entscheidet für eine Grammatik in CNF und ein Wort x=x1⋯xnx = x_1 \cdots x_n mit n≥1n \ge 1, ob x∈L(G)x \in L(G) ist. Er berechnet für jedes Teilwort xi⋯xjx_i \cdots x_j die Menge V(i,j)V(i, j) aller Variablen, aus denen es ableitbar ist.

Die Idee: Aus AA wird ein Wort der Länge mindestens 22 nur über eine Regel A→BCA \to BC abgeleitet. Dann leitet BB einen vorderen Teil xi⋯xkx_i \cdots x_k und CC den Rest xk+1⋯xjx_{k+1} \cdots x_j ab. Also ist A∈V(i,j)A \in V(i, j) genau dann, wenn es eine Regel A→BCA \to BC und ein kk mit i≤k<ji \le k < j gibt, sodass B∈V(i,k)B \in V(i, k) und C∈V(k+1,j)C \in V(k + 1, j). Kürzere Teilwörter kommen zuerst dran; das ist dynamische Programmierung.

ZeileEinrückungAnweisung
10for i = 1 to n:\texttt{for i = 1 to n:}
21V[i,i] = {A : A -> x_i ist Regel}\texttt{V[i,i] = \{A : A -> x\_i ist Regel\}}
30for l = 2 to n:\texttt{for l = 2 to n:}
41for i = 1 to n-l+1:\texttt{for i = 1 to n-l+1:}
52j = i+l-1; V[i,j] = {}\texttt{j = i+l-1; V[i,j] = \{\}}
62for k = i to j-1:\texttt{for k = i to j-1:}
73for jede Regel A -> BC:\texttt{for jede Regel A -> BC:}
84if B in V[i,k] and C in V[k+1,j]: fu¨ge A zu V[i,j] hinzu\texttt{if B in V[i,k] and C in V[k+1,j]: füge A zu V[i,j] hinzu}
90return S in V[1,n]\texttt{return S in V[1,n]}

Das leere Wort prüft man getrennt: Es liegt genau dann in L(G)L(G), wenn S→εS \to \varepsilon eine Regel ist.

Beispiel

CYK für aabbabaabbab

Grammatik: die CNF von GDG_D. Zeile ℓ\ell der Tabelle enthält die Mengen V(i,i+ℓ−1)V(i, i + \ell - 1) der Teilwörter der Länge ℓ\ell, Spalte ii deren Anfangsposition. Das Wort ist x1⋯x6=a a b b a bx_1 \cdots x_6 = a\,a\,b\,b\,a\,b; das Zeichen ∅\emptyset steht für die leere Menge.

Längei=1i = 1i=2i = 2i=3i = 3i=4i = 4i=5i = 5i=6i = 6
1AAAABBBBAABB
2∅\emptysetS0,SS_0, S∅\emptyset∅\emptysetS0,SS_0, S
3∅\emptysetXX∅\emptyset∅\emptyset
4S0,SS_0, S∅\emptyset∅\emptyset
5∅\emptyset∅\emptyset
6S0,SS_0, S

Einige Einträge im Detail. V(2,3)V(2, 3): Teilwort abab, einzige Aufteilung k=2k = 2 mit A∈V(2,2)A \in V(2, 2), B∈V(3,3)B \in V(3, 3); die Regeln S→ABS \to AB und S0→ABS_0 \to AB liefern S,S0S, S_0. V(2,4)V(2, 4): Teilwort abbabb; für k=3k = 3 ist S∈V(2,3)S \in V(2, 3) und B∈V(4,4)B \in V(4, 4), also XX wegen X→SBX \to SB. V(1,4)V(1, 4): für k=1k = 1 ist A∈V(1,1)A \in V(1, 1) und X∈V(2,4)X \in V(2, 4), also S,S0S, S_0. V(1,6)V(1, 6): für k=4k = 4 ist S∈V(1,4)S \in V(1, 4) und S∈V(5,6)S \in V(5, 6), also S,S0S, S_0 wegen S→SSS \to SS und S0→SSS_0 \to SS. Weil S0∈V(1,6)S_0 \in V(1, 6), gilt aabbab∈L(GD)aabbab \in L(G_D).

Kurz geprüft

Im CYK-Algorithmus für ein Wort der Länge 66: Wie viele Aufteilungspunkte kk werden für das Feld V(1,6)V(1, 6) geprüft?

Satz

Pumping-Lemma für kontextfreie Sprachen

Ist LL kontextfrei, dann gibt es ein n≥1n \ge 1, sodass jedes z∈Lz \in L mit ∣z∣≥n|z| \ge n eine Zerlegung z=uvwxyz = uvwxy hat mit

  • ∣vx∣≥1|vx| \ge 1 und ∣vwx∣≤n|vwx| \le n,
  • uviwxiy∈Lu v^i w x^i y \in L für alle i≥0i \ge 0.

Hier wird an zwei Stellen gleichzeitig gepumpt. Die Idee: Ist zz lang genug, hat der Ableitungsbaum zu einer CNF-Grammatik einen Pfad, auf dem mehr Variablen liegen, als die Grammatik hat. Eine Variable AA kommt doppelt vor. Den Teilbaum unter dem oberen AA kann man durch den unter dem unteren ersetzen oder umgekehrt; vv und xx sind die Teile, die dabei verschwinden oder sich wiederholen.

Anwendung: L={anbncn:n≥0}L = \{a^n b^n c^n : n \ge 0\} ist nicht kontextfrei. Zum gegebenen nn wähle z=anbncnz = a^n b^n c^n. Für jede Zerlegung mit ∣vwx∣≤n|vwx| \le n kann vwxvwx nicht zugleich ein a und ein c enthalten, denn dazwischen stehen nn Zeichen b. Mit i=0i = 0 entsteht uwyuwy: Es hat weniger als 3n3n Zeichen (wegen ∣vx∣≥1|vx| \ge 1), aber von dem Buchstaben, den vwxvwx nicht berührt, noch alle nn. Also kommen nicht alle drei Buchstaben gleich oft vor, und uwy∉Luwy \notin L.

Zusammenfassung

  • Eine kontextfreie Grammatik hat Regeln A→αA \to \alpha mit einer einzelnen Variablen links; sie erzeugt etwa {anbn}\{a^n b^n\}, Klammerwörter und Palindrome.

  • Ein Ableitungsbaum zeigt die Struktur eines Wortes. Zu jedem Baum gehört genau eine Links- und genau eine Rechtsableitung.

  • Mehrdeutig ist eine Grammatik, wenn ein Wort zwei verschiedene Bäume hat; für Ausdrücke behebt man das mit einer Variablen pro Vorrangstufe.

  • Jede kontextfreie Grammatik lässt sich in Chomsky-Normalform bringen: neues Startsymbol, ε-Regeln und Kettenregeln entfernen, Terminale auslagern, lange Regeln aufspalten.

  • Der CYK-Algorithmus füllt eine Tabelle V(i,j)V(i, j) von kurzen zu langen Teilwörtern und entscheidet x∈L(G)x \in L(G) in O(n3)O(n^3) bei fester Grammatik.

  • Das Pumping-Lemma für kontextfreie Sprachen pumpt zwei Teile v,xv, x gleichzeitig; damit ist {anbncn}\{a^n b^n c^n\} nicht kontextfrei.

Übungen

Aufgabe 1Multiple Choice

Welches Wort erzeugt GDG_D mit S→aSb∣SS∣εS \to aSb \mid SS \mid \varepsilon?

Aufgabe 2Multiple Choice

Welche Regel ist in Chomsky-Normalform nicht erlaubt (Variablen groß, Terminale klein)?

Aufgabe 3Numerisch

Wie viele verschiedene Ableitungsbäume hat das Wort a+a+a+aa + a + a + a in der Grammatik E→E+E∣aE \to E + E \mid a?

Aufgabe 4Freitext

Führe den CYK-Algorithmus mit der CNF von GDG_D (S0→AX∣AB∣SS∣εS_0 \to AX \mid AB \mid SS \mid \varepsilon, S→AX∣AB∣SSS \to AX \mid AB \mid SS, X→SBX \to SB, A→aA \to a, B→bB \to b) für das Wort abbaabba durch. Gib die ganze Tabelle an und entscheide.

Aufgabe 5Freitext

Beweise, dass die Grammatik S→aSb∣εS \to aSb \mid \varepsilon genau die Sprache {anbn:n≥0}\{a^n b^n : n \ge 0\} erzeugt.

Aufgabe 6Freitext

Bringe die Grammatik S→aSa∣bSb∣εS \to aSa \mid bSb \mid \varepsilon (Palindrome gerader Länge) in Chomsky-Normalform. Gib die Grammatik nach jedem der fünf Schritte an.