\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{ngerman}
\usepackage{fullpage}
\usepackage{eurosym}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {graphicx}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Satz}
\newtheorem {inv}[theorem] {Invariante}
\newtheorem {fact}[theorem] {Fakt}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {obs}[theorem] {Beobachtung}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}
\newtheorem {definition}[theorem] {Definition}


\title{Chomsky Normalform}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Wir illustrieren den Algorithmus, der eine kontextfreie Grammatik
in Chomsky Normalform \"uberf\"uhrt. Ausgangspunkt ist die Grammatik
mit $V = \{S,A,B,C,D\}$, $\Sigma = \{a,b\}$ und den folgenden Produktionen:
\begin{align*}
S &\to aAa \ | \ bBb \\
A &\to C \ | \ a\\
B &\to C \ | \ b\\
C &\to CD \ | \ \varepsilon\\
D &\to A \ | \ B \ | \ ab
\end{align*}

\paragraph{Schritt 1: Trennen der Terminalsymbole.}
F\"ur jedes Terminalsymbol $\sigma \in \Sigma$
f\"uhren wir eine neue Variable $V_\sigma$ ein und ersetzen
jedes Vorkommen von $\sigma$ durch $V_\sigma$.
Danach f\"ugen wir f\"ur jedes $\sigma \in \Sigma$ die 
neue Produktion $V_\sigma \to \sigma$ hinzu.
\begin{align*}
S &\to V_aA V_a \ | \ V_bBV_b \\
A &\to C \ | \ V_a\\
B &\to C \ | \ V_b\\
C &\to CD \ | \ \varepsilon\\
D &\to A \ | \ B \ | \ V_a V_b\\
V_a &\to a  \qquad 
V_b \to b \\
\end{align*}

\paragraph{Schritt 2: Aufl\"osen von langen Produktionen.}
F\"ur jede Produktion der Form $X \to Y_1 Y_2 \dots Y_k$ mit
$k \geq 3$ f\"uhren wir neue Variablen $Z_2, Z_3, \dots, Z_{k-1}$
ein und ersetzen $X \to Y_1 Y_2 \dots Y_k$ durch
$X \to Y_1Z_2$, $Z_2 \to Y_2Z_3$, $\dots$, $Z_{k-1} \to  Y_{k-1}Y_{k}$.

\begin{align*}
S &\to V_a E \ | \ V_b F \\
A &\to C \ | \ V_a\\
B &\to C \ | \ V_b\\
C &\to CD \ | \ \varepsilon\\
D &\to A \ | \ B \ | \ V_a V_b\\
E &\to AV_a\\
F &\to BV_b\\
V_a &\to a \qquad 
V_b \to b \\
\end{align*}


\paragraph{Schritt 3: Beseitigen der $\varepsilon$-Produktionen.}
  Zun\"achst bestimmen wir alle Variablen, aus denen sich $\varepsilon$
  Ableiten l\"asst. Dazu markieren wir zun\"achst alle Variablen $X$,
  f\"ur die es eine Regel $X \to \varepsilon$ gibt.
  In unserem Beispiel wird $C$ markiert. 
  
  Dann wiederholen wir
  die folgende Regel, solange es geht: wenn eine unmarkierte
  Variable $X$ existiert, so dass auf der rechten Seite einer Produktion
  $X \to \alpha$ nur markierte Variablen vorkommen, markiere $X$.

  In unserem Beispiel markieren wir $A$ und $B$ (wegen $A \to C$ und
  $B \to C$) und dann $D$ (wegen $D \to A$).  Zum Schluss sind 
  $A$, $B$, $C$ und $D$ markiert, und das sind genau die
  Variablen, aus denen man $\varepsilon$ ableiten kann.

  Schlie\ss{}lich betrachten wir jede Produktion der Form $X \to YZ$.
  Wenn $Y$ markiert ist, f\"ugen wir die Produktion $X \to Z$ hinzu,
  wenn $Z$ markiert ist, f\"ugen wir die Produktion $X \to Y$ hinzu.
  Dann l\"oschen wir die Produktionen $X \to \varepsilon$.

\begin{align*}
S &\to V_a E \ | \ V_b F \\
A &\to C \ | \ V_a\\
B &\to C \ | \ V_b\\
C &\to CD \ | \ C \ | \ D \\
D &\to A \ | \ B \ | \ V_a V_b\\
E &\to AV_a \ | \ V_a \\
F &\to BV_b \ | \ V_b \\
V_a &\to a \qquad 
V_b \to b \\
\end{align*}

\paragraph{Schritt 4: Beseitigen der Kettenregeln.}
Zun\"achst m\"ussen wir Kreise der Form 
$X_1 \to X_2 \to X_3 \to \dots \to X_1$ beseitigen.
Die aktuelle Grammatik enth\"alt den Kreis 
$A \to C \to D \to B \to C \to D \to A$. Wir f\"uhren eine
neue Variable $G$ ein und ersetzen alle Vorkommen von $A$, $B$, $C$, $D$
durch $G$.
\begin{align*}
S &\to V_a E \ | \ V_b F \\
G &\to G \ | \ V_a\\
G &\to G \ | \ V_b\\
G &\to GG \ | \ G \ | \ G \\
G &\to G \ | \ G \ | \ V_a V_b\\
E &\to GV_a \ | \ V_a \\
F &\to GV_b \ | \ V_b \\
V_a &\to a \qquad 
V_b \to b \\
\end{align*}
Dann beseitigen wir alle Regeln der Form $G \to G$.
\begin{align*}
S &\to V_a E \ | \ V_b F \\
G &\to  GG  \ | \ V_a \ | \ V_b \ | \ V_aV_b\\
E &\to GV_a \ | \ V_a \\
F &\to GV_b \ | \ V_b \\
V_a &\to a \qquad 
V_b \to b \\
\end{align*}
Jetzt enth\"alt die Grammatik keine Kreise mehr. Wir ordnen die Variablen so,
dass bei jeder Kettenregel $X \to Y$ die Variable $X$ vor der Variablen
$Y$ kommt. Eine solche Ordnung ist zum Beispiel
$S, G, E, F, V_a, V_b$. (Eine andere g\"ultige Ordnung w\"are
$S, F, E, G, V_a, V_b$, aber nicht $S, E, G, V_a, V_b, F$, da es die
Regel $F \to V_b$ gibt). 

Dann gehen wir die Variablen in umgekehrter Reihenfolge
durch. F\"ur jede Variable $X$  ersetzen wir jede Kettenregel 
$X \to Y$ durch neue Produktionen der Form $X \to \alpha$,
f\"ur alle Produktionen $Y \to \alpha$.

In unserem Beispiel tun wir also folgendes: 
Wir betrachten zun\"achst $V_b$. Es ist nichts zu tun, weil es keine Produktion der 
Form $V_b \to X$, $X$ Variable, gibt. 

Dann betrachten wir $V_a$, wo es genauso
aussieht. 

Dann betrachten wir $F$. Es gibt die Produktion $F \to V_b$. Wir ersetzen sie durch
$F \to b$, da es die Produktion $V_b \to b$ gibt.

Dann kommt $E$, wo wir $E \to V_a$ durch $E \to a$ ersetzen.

Danach ist $G$ an der Reihe. Wir ersetzen $G \to V_a$ durch $G \to a$ und
$G \to V_b$ durch $G \to b$.

Zum Schluss kommt $S$, wo nichts zu tun ist.

Die resultierende Grammatik ist in Chomsky Normalform:
\begin{align*}
S &\to V_a E \ | \ V_b F \\
G &\to  GG  \ | \ a \ | \ b \ | \ V_aV_b\\
E &\to GV_a \ | \ a \\
F &\to GV_b \ | \ b \\
V_a &\to a \qquad 
V_b \to b \\
\end{align*}

\end{document}