Eine Grammatik mit ist in Chomsky-Normalform gegeben, wenn alle Regeln eine der beiden Formen Misplaced &A & \rightarrow BC \\ A & \rightarrow a \end{align}$$ haben, wobei $A, B, C \in V$ und $a \in \Sigma$. > [!Note] Satz > > Zu jeder [[Chomsky-Hierachie|kontextfreien]] [[Grammatik]] $G$ mit $\epsilon \notin L(G)$ gibt es eine Grammatik $G'$ in Chomsky-Normalform mit $L(G) = L(G')$. ## Beispiel $$\begin{align} S & \rightarrow AB \\ S & \rightarrow ABA \\ A & \rightarrow aA \\ A & \rightarrow a \\ B & \rightarrow Bb \\ B & \rightarrow b \ | \ \epsilon \end{align}$$ Sprache Epsilon-frei machen: Epsilon-Regelung vorziehen: $$\begin{align} S & \rightarrow AB \ \color{green}| \ A \\ S & \rightarrow ABA \ \color{green}| \ AA \\ A & \rightarrow aA \\ A & \rightarrow a \\ B & \rightarrow Bb \ \color{green}| \ b \\ B & \rightarrow \color{green}b \end{align}$$ Algorithmus anwenden: 1. Zyklen eliminieren: Keine Zyklen vorhanden EIn Zyklus wäre z.B: $X_1 \rightarrow X_2 | a, X_2 \rightarrow X_1 | b$, dieser kann aufgelöst werden wenn man alle $X_n$ in der Grammatik durch $X$ ersetzt und dann die Regel $X \rightarrow a | b$ einführt. So ein Zyklus existiert in diesem Fall bei unserem Beispiel nicht, deshalb kann dieser Schritt abgehakt werden. 3. Variablen transformieren und sortieren $$\begin{align} A_0 & \rightarrow A_1 A_2 \ | \ {\color{green}A_1} \ | \ A_1 A_2 A_1 \ | \ A_1 A_1 \\ A_1 & \rightarrow a A_1 \ | \ a \\ A_2 & \rightarrow A_2 b \ | \ b \end{align}$$ **Einserregel:** Es darf kein Nichtterminal alleine stehen, deswegen ersetzen mit seiner Ableitung: $$\begin{align} A_0 & \rightarrow A_1 A_2 \ | \ {\color{green}a A_1 \ | \ a} \ | \ A_1 A_2 A_1 \ | \ A_1 A_1 \\ A_1 & \rightarrow a A_1 \ | \ a \\ A_2 & \rightarrow A_2 b \ | \ b \end{align}$$ 3. Eliminieren von Terminalsymbolen: $$\begin{align} \color{green}A' & \color{green}\rightarrow a \\ \color{green}B' & \color{green}\rightarrow b \\ A_0 & \rightarrow A_1 A_2 \ | \ {\color{green}A'} A_1 \ | \ a \ | \ A_1 A_2 A_1 \ | \ A_1 A_1 \\ A_1 & \rightarrow {\color{green}A'} A_1 \ | \ a \\ A_2 & \rightarrow A_2 {\color{green}B'} \ | \ b \end{align}$$ 4. Ketten aufbrechen die länger als 2 sind: $$\begin{align} & A_0 & \rightarrow \underbrace{A_1 A_2 A_1}_{k = 3} \\ \\ \Rightarrow k - 2 = 1 \text{ Zusatzregel: } \quad & A_0 & \rightarrow A_1 \color{green}C_1 \\ & C_1 & \rightarrow A_2 A_1 \end{align}$$ > [!link] Siehe auch > > [[Chomsky-Hierachie]]