Inhalt

Praktikum objektorientiertes Programmieren: CNF

Inhalt

Spezifikation

Theorie

In diesen Abschnitt beschreiben wir den theoretischen Hintergrund, der für die meisten kontextfreien Grammatiken die Existenz einer äquivalenten reduzierten kontextfreien Grammatik in Chomsky-Normalform ohne Ketten- und ohne $\epsilon$-Produktionen begründet. Wir orientieren uns an den entsprechenden Beweisen in [2] und verwenden die dort benutzten Konstruktionen, um Algorithmen abzuleiten.

Das generelle Umfeld sind Sprachen als Teilmengen der Wortmengen über gegebenen Alphabeten, für die Regelsysteme zur Beschreibung verwendet werden. Dabei sind Alphabetzeichen Wörter und die Wortmenge über einem Alphabet ist der Abschluss gegenüber einer assoziativen binären Operation o (Konkatenation), die zusammen mit der Wortmenge und dem neutralen Element $\epsilon$ ein Monoid bildet. Wir schreiben für poq im folgenden immer pq.

Definition 1 (kontextfreie Grammatik)   Eine kontextfreie Grammatik G ist ein 4-Tupel G = (M, A, R, S) mit

• M, A nichtleere endliche disjunkte Mengen,
• R $\subseteq$ M×$\left(\vphantom{M\cup A}\right.$M $\cup$ A$\left.\vphantom{M\cup A}\right)^{\star}_{}$ endlich,
• S $\in$ M.

Dabei wird M als Menge der Metazeichen oder Nichtterminale bezeichnet, A als Menge der Alphabetzeichen oder Terminale, R heisst die Regelmenge, ihre Elemente (u, v) Produktionen und S wird Startsymbol genannt.

Definition 2 (Äquivalenz)   Für Wörter p, q $\in$ A^$\star$ heisst q direkt ableitbar aus p (p $\vdash$ q), wenn eine Regel (u, v) $\in$ R und Wörter s, t $\in$ (M $\cup$ A)^$\star$ existieren, mit p = sut und q = svt. q heisst ableitbar aus p, wenn (p, q) in $\vdash^{\star}_{}$ = $\bigcup_{i\geq 0}^{}$ $\vdash^{i}_{}$, der reflexiven transitiven Hülle von $\vdash$ liegt.

Die Menge L(G) = $\left\{\vphantom{w \mid w\in A^\star\mbox{ und }S\vdash^\star w}\right.$w | w $\in$ A^$\star$ und S $\vdash^{\star}_{}$ w$\left.\vphantom{w \mid w\in A^\star\mbox{ und }S\vdash^\star w}\right\}$ aller aus dem Startsymbol S ableitbaren Wörter über A heisst die von G erzeugte Sprache.

Zwei Grammatiken G und G' heissen äquivalent, wenn sie die gleichen Sprachen erzeugen, also L(G) = L(G') gilt.

Definition 3 (reduzierte Grammatik)   Wenn G = (M, A, R, S) eine kontextfreie Grammatik ist, dann heisst m $\in$ M produktiv, wenn ein w $\in$ A^$\star$ existiert mit m $\vdash^{\star}_{}$ w. Das Symbol m $\in$ M heisst erreichbar, wenn p, q $\in$ (M $\cup$ A)^$\star$ mit S $\vdash^{\star}_{}$ pmq existieren und G heisst reduziert, wenn alle m $\in$ M produktiv und erreichbar sind.

Satz 1   Zu jeder kontextfreien Grammatik G = (M, A, R, S) mit L(G) $\neq$ $\emptyset$ existiert eine äquivalente reduzierte kontextfreie Grammatik G' = (M', A', R', S).

Der Beweis findet sich in [2, Satz 4.2]. Dort werden im ersten Schritt die Menge aller produktiven und im zweiten die Menge aller erreichbaren Metazeichen effektiv berechnet (Algorithmen 1 und 2), die Korrektheit der angegebenen Algorithmen bewiesen und es wird gezeigt, dass eine Nacheinanderausführung zu einer reduzierten äquivalenten Grammatik führt.

Algorithmus 1 zur Berechnung der Menge M_p aller produktiven Metazeichen nimmt natürlich alle Metazeichen, aus denen ein Wort aus A^$\star$ direkt abgeleitet werden kann in M_p auf. Anschliessend wird M_p abgeschlossen gegenüber $\vdash$, d.h. mit allen Regeln, die (in beiden Komponenten) Nichtterminale ausschliesslich aus M_p haben, können lediglich Wörter abgeleitet werden, die ebenfalls Nichtterminale ausschliesslich aus M_p haben.

Nach Berechnung von M_p können alle Produktionen entfernt werden, die Symbole aus M $\setminus$ M_p enthalten. Es ergibt sich eine äquivalente Grammatik mit ausschliesslich produktiven Metazeichen.

Algorithmus 2 zur Berechnung der Menge M_e der erreichbaren Metazeichen lässt sich am einfachsten rekursiv formulieren: Das Startzeichen S ist erreichbar und alle Zeichen sind erreichbar, die auf einer rechten Seite einer Produktion stehen, auf deren linker Seite ein erreichbares Zeichen steht.

Nach Berechnung von M_e können alle Produktionen gelöscht werden, deren linke Seite aus M $\setminus$ M_e ist, es ergibt sich eine äquivalente Grammatik mit ausschliesslich erreichbaren Zeichen.

Definition 4 ($\epsilon$- und Kettenproduktionen)   Sei G = (M, A, R, S) eine kontextfreie Grammatik. Dann heissen Produktionen (u, v) $\in$ R

• $\epsilon$-Produktion, falls v = $\epsilon$ und
• Kettenproduktion, falls v $\in$ M.

Satz 2   Zu jeder kontextfreien Grammatik G = (M, A, R, S) mit L(G) $\neq$ $\emptyset$ existiert eine reduzierte kontextfreie Grammatik G' = (M', A', R', S) ohne $\epsilon$-Produktionen mit L(G') = L(G) $\setminus$ $\left\{\vphantom{\epsilon}\right.$$\epsilon$$\left.\vphantom{\epsilon}\right\}$.

Im Beweis in [2, Satz 4.3] werden Zeichen m $\in$ M nullierbar genannt, wenn m $\vdash^{\star}_{}$ $\epsilon$ gilt. Es genügt dann (nach Berechnung einer reduzierten Grammatik), alle nullierbaren Symbole zu berechnen und daraus eine neue Regelmenge zu konstruieren.

Der Algorithmus 3 berechnet die Menge M_n aller nullierbaren Nichtterminale: Alle m $\in$ M mit (m,$\epsilon$) $\in$ R sind nullierbar. Wenn (u, v) $\in$ R und alle Symbole aus v nullierbar sind, dann ist u nullierbar. Bilden wir darüber den Abschluss, erhalten wir alle nullierbaren Symbole.

Mit M_n kann die Menge R' der neuen Produktionen (ohne $\epsilon$-Produktion) berechnet werden: Wenn (m, v₁v₂...v_k) $\in$ R, dann füge alle Produktionen (m, v₁'v₂'...v_k') zu R' hinzu, wobei gilt:

• wenn v_i nicht nullierbar ist, dann gilt v_i' = v_i,
• wenn v_i nullierbar ist, dann ist v_i' entweder v_i oder $\epsilon$ und
• nicht alle v_i' sind gleich $\epsilon$.

Mit anderen Worten heisst das: Für jede Teilmenge der Menge der nullierbaren Zeichen auf einer rechten Seite wird eine neue Regel erzeugt, bei der diese Teilmenge aus der rechten Seite gestrichen wurde. Falls dabei nicht alle Zeichen gestrichen wurden, wird die neue Regel in die Regelmenge aufgenommen.

Satz 3   Zu jeder kontextfreien Grammatik G = (M, A, R, S) mit L(G) $\neq$ $\emptyset$ und L(G) $\cap$ $\left\{\vphantom{\epsilon}\right.$$\epsilon$$\left.\vphantom{\epsilon}\right\}$ = $\emptyset$ existiert eine äquivalente reduzierte kontextfreie Grammatik G' = (M', A', R', S) ohne $\epsilon$- und ohne Kettenproduktionen.

Zur Entfernung der Kettenproduktionen wird für jedes Metazeichen m die Menge der durch m substituierbaren Metazeichen ermittelt, indem in der Teilmenge der Produktionen, die Kettenproduktionen sind, die von m aus erreichbaren Zeichen ermittelt werden. Dazu kann Algorithmus 2 verwendet werden. Gilt dann m $\vdash$ m₁ $\vdash$...$\vdash$ m_k $\vdash$ m' mit m, m', m₁,..., m_k $\in$ M, dann können alle Regeln der Form (m', w) durch Regeln (m, w) ersetzt werden. Um eine äquivalente Grammatik zu erhalten, müssen noch alle Nicht-Kettenproduktionen in die neue Regelmenge aufgenommen werden. Algorithmus 4 fasst das zusammen.

Definition 5 (Chomsky-Normalform)   Eine kontextfreie Grammatik G heisst in Chomsky-Normalform, wenn für jede Produktion (u, v) $\in$ R gilt, dass u $\in$ M und v $\in$ M² $\cup$ A.

Satz 4   Zu jeder kontextfreien Grammatik G = (M, A, R, S) mit L(G) $\neq$ $\emptyset$ und L(G) $\cap$ $\left\{\vphantom{\epsilon}\right.$$\epsilon$$\left.\vphantom{\epsilon}\right\}$ = $\emptyset$ existiert eine äquivalente reduzierte Grammatik in Chomsky-Normalform ohne $\epsilon$- und ohne Kettenproduktionen.

Nach den vorangegangenen Sätzen existiert eine zu G äquivalente reduzierte Grammatik ohne $\epsilon$- und ohne Kettenproduktionen. Die Berechnung der Chomsky-Normalform vollzieht sich nun in zwei Schritten:

Zuerst wird die Regelmenge so manipuliert, dass alle Regeln entweder die Form (m, a) mit a $\in$ A oder die Form (m, w) mit w $\in$ M⁺ haben. Dazu wird jedes Auftreten von a aus A in einer rechten Seite durch a' ersetzt und die Regel a' $\rightarrow$ a hinzugefügt, wobei a' ein neues Metazeichen ist.

Nun werden alle Regeln der Form (m, w) mit w $\in$ M⁺ betrachtet. Es ist zu beachten, dass | w| $\geq$ 2 gilt, da G keine Kettenproduktionen enthält. Für | w| = 2 ist nichts zu tun und für | w| > 2 gilt w = m₁m₂...m_k. Dann wird (m, w) durch die beiden Regeln (m, m₁[m₂...m_k]) und ([m₂...m_k], m₂...m_k) ersetzt, wobei [m₂...m_k] ein neues Metazeichen ist und die rechten Seiten kürzer als die rechte Seite von (m, w).

Dieses Vorgehen ist in Algorithmus 5 zusammengefasst, dabei bezeichnet w[a/b] die simultane Ersetzung von a durch b in w und alle zu M hinzugefügten Zeichen seien neu.

Inhalt

Spezifikation

Inhalt

Praktikum objektorientiertes Programmieren: CNF