Normalformen und Word-Problem

Eine Kontextfreie Grammatik kann in mehrere Normalforman transformiert werden (Zur Erinnerung: eine kontextfreie Grammatik hat auf der linken Seite jeder Produktion genau eine Variable stehen, und nichts anderes). Die beiden bekanntesten sind die Chomsky- und die Greibach-Normalform:

Chomsky-Normalform

Jede Produktion hat eine der beiden folgenden Formen:

X -> YZ
X -> a

Also entweder stehen rechts zwei Variablen oder ein Terminalsymbol. Die Theorie besagt nun, dass jede CFG in diese Normalform umgewandelt werden kann. Man geht dabei einfach durch den folgenden Algorithmus:

Für jede Produktion wird überprüft, ob sie bereits eine der beiden oberen Formen aufweist. Wenn nicht, so splittet man den rechten Teil folgendermassen auf:
Besteht der rechte Teil aus einer einzelnen Variable (S -> X), so definiert man eine weitere Produktion E -> e, welche für die neue Variable E den Nullstring einsetzt und fügt dieses E bei der ursprünglichen Produktion hinten an: S -> XE.
Ansonsten teilt man den rechten Teil in zwei möglichst gleich grosse Teile auf (S -> vw), definiert zwei neue Produktionen A -> v und B -> w und ersetzt die ursprüngliche Produktion durch S -> AB.

Greibach-Normalform

Jede Produktion hat eine die folgende Forme:

X -> a w
wobei w ein Wort bestehend aus lauter Variablen (=V*) ist.

Die Theorie besagt wiederum, dass jede CFG in diese Normalform umgewandelt werden kann. Man geht dabei einfach durch den folgenden Algorithmus:

Für jede Produktion wird überprüft, ob sie bereits die obige Form aufweist. Wenn nicht, so passiert folgendes:
Man teilt den rechten Teil auf in das linkeste Element X und den gesamten Schwanz w: S -> Xw. Ist das Element X ein Terminalsymbol x, so kann w als Variable zusammengefasst und als neue Produktion hingeschrieben werden: S -> xY und Y -> w
Ist X eine Variable, so expandiert man diese Variable solange mittels der dazugehörigen Produkion X -> ?, bis dass an der linkesten Stelle Z dieser Expansion X ->* Zv seinerseits ein Terminalsymbol z steht. Die ursprüngliche Produktion wird sodann umgewandelt in S -> zvw.
Ergibt die Expansion X->*Zv niemals ein Terminalsymbol für Z, so kann die ganze Produktion gelöscht werden, da sie niemals zu einem gültigen Wort führen wird.

Das Wort-Problem

Das Wort-Problem ist schnell formuliert: Gegeben sei eine Grammatik und ein beliebiges Wort. Man entscheide nun, ob dieses Wort in der (durch die Grammatik gegebenen) Sprache drin ist.

Für Kontextfreie Grammatika ist dieses Problem lösbar, wobei man sich dabei der dynamischen Programmierung behilft. Man betrachte folgendes Beispiel: Gegeben sei folgende Grammatik in der Chromsky-Normalfom:

S -> AC     S -> BD
A -> 0      B -> 1
C -> 1      C -> BS      C -> AE
D -> 0      D -> AS      D -> BF
E -> CC     F -> DD

Und das Wort 001101

Sodann erstellt man eine Tabelle, in der man für jeden Buchstaben des Wortes einträgt, welche Produktionen diesen Buchstaben erstellen können:

+---------+---------+---------+---------+---------+---------+
|    0    |    0    |    1    |    1    |    0    |    1    |
+---------+---------+---------+---------+---------+---------+
| A -> 0  | A -> 0  | B -> 1  | B -> 1  | A -> 0  | B -> 1  |
| D -> 0  | D -> 0  | C -> 1  | C -> 1  | D -> 0  | C -> 1  |
+---------+---------+---------+---------+---------+---------+

Nachfolgend sei definiert, dass der Eintrag einer Zelle stets einen Teilstring des gesamten Strings bezeichnet. Der Beginn des Teilstrings ist dabei jeweils derjenige in der gleichen Spalte der Zelle und das Ende liegt rechts diagonal dazu (Dreieck).

In den nächsten Schritten fügt man der Tabelle stets eine Zeile mit einer Zelle weniger hinzu. In jede Zelle trägt man alle Produktionen ein, die zum zugehörigen Teilstring führen.

Dies entspricht in der zweiten Zeile einer Kombination der Variablen der oberen und obenrechten Zelle. Beispielsweise überprüft man in der linkesten Zelle, ob es eine Produktion gibt, die entweder AA, AD, DA oder DD herstellen kann. In diesem Beispiel existiert nur die Produktion F -> DD.

+---------+---------+---------+---------+---------+---------+
|    0    |    0    |    1    |    1    |    0    |    1    |
+---------+---------+---------+---------+---------+---------+
| A -> 0  | A -> 0  | B -> 1  | B -> 1  | A -> 0  | B -> 1  |
| D -> 0  | D -> 0  | C -> 1  | C -> 1  | D -> 0  | C -> 1  |
+---------+---------+---------+---------+---------+---------+
| F -> DD | S -> AC | E -> CC | S -> BD | S -> AC |
+---------+---------+---------+---------+---------+

In der nächsten Zeile betrachtet man die Wortlänge 3. Für die linkeste Zelle gibt es zwei Möglichkeiten, den zugrundeliegenden Teilstring zu generieren: Entweder mit der Produktion in der Zelle oberhalb plus den Produktionen, die zum dritten Buchstaben führen, oder aber den Produktionen, die zum ersten Buchstaben führen plus die Produktion rechtsoberhalb der aktuellen Zelle.

+---------+---------+---------+---------+---------+---------+
|    0    |    0    |    1    |    1    |    0    |    1    |
+---------+---------+---------+---------+---------+---------+
| A -> 0  | A -> 0  | B -> 1  | B -> 1  | A -> 0  | B -> 1  |
| D -> 0  | D -> 0  | C -> 1  | C -> 1  | D -> 0  | C -> 1  |
+---------+---------+---------+---------+---------+---------+
| F -> DD | S -> AC | E -> CC | S -> BD | S -> AC |
+---------+---------+---------+---------+---------+
| D -> AS | C -> AE | C -> BS | C -> BS |
+---------+---------+---------+---------+

Nun geht es weiter mit den Teilstring-Längen 4, 5 und 6, bei welchen stets überprüft wird, ob sie konstruiert werden können mittels eines Teilstrings der Zeile oberhalb plus einem Teilstring der Länge 1 in der obersten Zeile.

+---------+---------+---------+---------+---------+---------+
|    0    |    0    |    1    |    1    |    0    |    1    |
+---------+---------+---------+---------+---------+---------+
| A -> 0  | A -> 0  | B -> 1  | B -> 1  | A -> 0  | B -> 1  |
| D -> 0  | D -> 0  | C -> 1  | C -> 1  | D -> 0  | C -> 1  |
+---------+---------+---------+---------+---------+---------+
| F -> DD | S -> AC | E -> CC | S -> BD | S -> AC |
+---------+---------+---------+---------+---------+
| D -> AS | C -> AE | C -> BS | C -> BS |
+---------+---------+---------+---------+
| S -> AC | S -> AC | E -> CC |
+---------+---------+---------+
| D -> AS | C -> AE |
+---------+---------+
| S -> AC |
+---------+

Das Ergebnis dieses Algorithmus steht in der untersten Zeile. Befindet sich in dieser Zelle keine Produktion, die links das Startsymbol S enthält, so befindet sich das Wort nicht in der Sprache, ansonsten schon. Das Wort "001101" ist also in der Sprache enthalten. Hier ein weiteres Beispiel mit derselben Sprache:

+---------+---------+---------+---------+---------+---------+
|    1    |    0    |    1    |    0    |    1    |    1    |
+---------+---------+---------+---------+---------+---------+
| B -> 1  | A -> 0  | B -> 1  | A -> 0  | B -> 1  | B -> 1  |
| C -> 1  | D -> 0  | C -> 1  | D -> 0  | C -> 1  | C -> 1  |
+---------+---------+---------+---------+---------+---------+
| S -> BD | S -> AC | S -> BD | S -> AC | E -> CC |
+---------+---------+---------+---------+---------+
| C -> BS | D -> AS | C -> BS | C -> AE |
+---------+---------+---------+---------+
| S -> BD | S -> AC | E -> CC |
+---------+---------+---------+
| C -> BS | C -> AE |
+---------+---------+
| E -> CC |
+---------+

Dieses Wort kann nicht aus S heraus entstehen. Deshalb ist es nicht in der Sprache enthalten.

Kleine Anmerkung zum Schluss: Wenn eine Zelle zwischendrin mal keine passende Produktion hat, so heisst das noch lange nicht, dass das ganze Wort nicht doch in der Sprache enthalten sein könnte. Kleines Beispiel dazu:

Grammatik:
S -> AB
A -> NB
B -> 1
N -> 0

Das einzige gültige Wort ist "011" und hier ist die Tabelle:

+---------+---------+---------+
|    0    |    1    |    1    |
+---------+---------+---------+
| N -> 0  | B -> 1  | B -> 1  |
+---------+---------+---------+
| A -> NB |    -    |
+---------+---------+
| S -> AB |
+---------+