Löst Wortproblem für kontextfreie Grammatiken Dafür muss die kontextfreie Grammatik in Chomsky-Normalform sein. Beispiel Misplaced &S & \rightarrow BS \ | \ \text{a} \ | \ \text{b} \\ A & \rightarrow BB \ | \ \text{c} \ | \ \text{b} \\ B & \rightarrow CA \ | \ AA \ | \ AB \ | \ \text{a} \\ C & \rightarrow \text{c} \end{align}$$ $w = \text{ababc} \in L$? ![[cyk_a.jpg]] $S \notin \emptyset \Rightarrow w \notin L$ Ausführliches Beispiel Gegeben ist die Grammatik in Chomsky-Normalform für die kontextfreie Sprache : Misplaced &S & \rightarrow AB \ | \ CD \ | \ AD \\ C & \rightarrow AB \ | \ SC \\ D & \rightarrow BC \ | \ AD \ | \ BB \\ A & \rightarrow \text{a} \\ B & \rightarrow \text{b} \end{align}$$ Es soll untersucht werden, ob das Wort $w = \text{abbab}$ in $L$ enthalten ist. **Algorithmus:** Dazu erstelle man sich eine Pyramidentabelle, bei der die Basis genau so viele Zellen hat wie das Wort Buchstaben. **Letzte Zeile** In die untersten Zellen schreibt man jeweils, aus welchen Nichtterminalen der Buchstabe abgeleitet werden kann. In unserem Fall ist das bei $\text{a}$ nur $A$ und bei $\text{b}$ nur $B$. ![[cyk_0.jpg]] **Vorletzte Zeile** Für die erste Zelle suchen wir Nichtterminale, die $AB$ ableiten können. In unserer Grammatik ist das bei $S$ und $C$ der fall, deswegen schreiben wir diese in die Zelle. **Sonderfall keine Ableitungen:** Bei der dritten Zelle suchen wir Nichtterminale, die $BA$ ableiten können. In unserer Grammatik existieren aber keine Nichtterminale, die das können, deswegen schreiben wir $\emptyset$ in die Zelle. **Restliche Zeilen** ![[cyk_1.jpg]] Für die erste Zelle der dritten Zeile setzen wir einen "Marker" auf die Zelle links darunter (zeigt in unserem Fall auf $S, C$), für den anderen Marker gehen wir ganz rechts runter (zeigt in unserem Fall auf $B$). Jetzt suchen wir wieder Nichtterminale, die die kombinationen dieser Zellen ableiten können: Für $SB$ gibt es keine, genauso gibt es keine für $CB$. Jetzt bewegen wir unsere Marker: Der linke Marker wandert eins nach links unten (zeigt in unserem Fall dann auf $A$), der rechte eins links hoch (zeigt in unserem Fall dann auf $D$): Dann suchen wir wieder Nichtterminale die die Kombinationen ableiten können: Hier gibt es nur die Kombination $AD$. Diese Kombination kann von $S$ und von $D$ abgeleitet werden. Deswegen schreiben wir in die Zelle $S, D$. Dieses "Markerverschieben" wiederholen wir bis der linke Marker ganz unten und der rechte Marker ganz oben ist. In unserem Fall ist das schon so, deswegen können wir hier aufhören. **Sonderfall leere Menge**: Falls in einer Kombination ein Teil eine leere Menge ist, können wir diese überspringen. **Ergebnis** Wenn in der Spitze der Pyramide das Startsymbol ist, ist das Wort teil der Sprache. ![[cyk_2.jpg]] In unserem Fall: $S \in \{C, S\} \Rightarrow w \in L$