tutorium11.tex

\include{includes/common_start}
\tutnr{11}

\section{Chomsky-Normalform}
\subsection{Chomsky-Normalform}
\frame{
\frametitle{Chomsky-Normalform}
Der Cocke-Younger-Kasami-Algorithmus (CYK) löst das Wortproblem für kontextfreie Sprachen (CH-2) in $\O{n^3}$.
Um CYK anzuwenden, muss die gegebene Grammatik erst in Chomsky-Normalform gebracht werden. Das ist für jede CH-2-Grammatik möglich.
\
\begin{exampleblock}{Chomsky-Normalform}
Eine CH-2-Grammatik \textit{G} $= (\Sigma,\mathcal{V,S,R) }$ ist in Chomsky-Normalform,  wenn jede Produktion aus $\mathcal{R}$ eine der folgenden Formen hat:
\begin{itemize}
\item  $A \rightarrow BC$
\item  $A \rightarrow a$
\end{itemize}
Wobei gilt $A,B,C\in\mathcal{V}$ und $a \in \Sigma$.
Um das leere Wort in der Sprache zu erlauben, lässt sich die Grammatik leicht mit neuem Startsymbol $S'$ ergänzen mit der Regel $$ S' \rightarrow S \mid \varepsilon $$
\end{exampleblock}
}


%\subsection{Umwandlung in Chomsky-Normalform}
\frame{
\frametitle{Umwandlung in Chomsky-Normalform}
\begin{enumerate}
\item Für alle $\textcolor{red}{a} \in \Sigma$ und für alle Produktionen, auf deren rechter Seite $\textcolor{red}{a}$ vorkommt 
(außer für $V  \rightarrow \textcolor{red}{a}$, mit $V \in\mathcal{V}$),
wird jedes Vorkommen von $\textcolor{red}{a}$ durch ein \emph{neues} Nichtterminalsymbol $\textcolor{blue}{A}$ ersetzt
%(und $A$ in die Variablenmenge aufgenommen)
und die Produktion $\textcolor{blue}{A} \rightarrow \textcolor{red}{a}$ wird hinzugefügt.
\end{enumerate}

\begin{exampleblock}{Umwandlungsbeispiel (Schritt 1 von 4)}
\begin{columns}[c]
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY\\
X &\rightarrow \textcolor{red}{a}X\textcolor{red}{b} \mid Z \mid \varepsilon\\
Y &\rightarrow \textcolor{red}{cc}Y \mid \varepsilon\\
Z &\rightarrow X\\
\end{align*}
\end{column}
%
\
\begin{column}{0.05\textwidth}
$\Rightarrow$
\end{column}
%
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY\\
X &\rightarrow \textcolor{blue}{A}X\textcolor{blue}{B} \mid Z \mid \varepsilon\\
Y &\rightarrow \textcolor{blue}{CC}Y \mid \varepsilon\\
Z &\rightarrow X\\
\textcolor{blue}{A} &\rightarrow \textcolor{red}{a}\\
\textcolor{blue}{B} &\rightarrow \textcolor{red}{b}\\
\textcolor{blue}{C} &\rightarrow \textcolor{red}{c}\\
\end{align*}
\end{column}
\end{columns}
\end{exampleblock}
}

\frame{
\frametitle{Umwandlung in Chomsky-Normalform}
\begin{enumerate}
\setcounter{enumi}{1}
\item
Für Produktionen mit mehr als zwei
Variablen rechts werden \textcolor{blue}{ \emph{neue} Nichterminale} eingeführt
und dazu \textcolor{blue}{passende Produktionen} hinzugefügt.
\end{enumerate}

\begin{exampleblock}{Umwandlungsbeispiel (Schritt 2 von 4)}
\begin{columns}[c]
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY\\
X &\rightarrow \textcolor{red}{AXB} \mid Z \mid \varepsilon \\
Y &\rightarrow \textcolor{red}{CCY} \mid \varepsilon \\
Z &\rightarrow X\\
A &\rightarrow a\\
B &\rightarrow b\\
C &\rightarrow c\\
\end{align*}
\end{column}
%
\
\begin{column}{0.05\textwidth}
$\Rightarrow$
\end{column}
%
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY\\
X &\rightarrow \textcolor{blue}{FB} \mid Z \mid \varepsilon \\
Y &\rightarrow \textcolor{blue}{GY} \mid \varepsilon \\
Z &\rightarrow X\\
\textcolor{blue}{F} &\rightarrow \textcolor{blue}{AX}\\
\textcolor{blue}{G} &\rightarrow \textcolor{blue}{CC}\\
A &\rightarrow a\\
B &\rightarrow b\\
C &\rightarrow c\\
\end{align*}
\end{column}
\end{columns}
\end{exampleblock}
}

\begin{frame}
\frametitle{Umwandlung in Chomsky-Normalform}
\begin{enumerate}
\setcounter{enumi}{2}
\item Entfernen von Produktionen der Form $\textcolor{red}{V} \rightarrow \textcolor{red}{\varepsilon}$
f"ur $V \in \mathcal{V}, v \neq \mathcal{S}$ \\ $\Rightarrow$ "`Vorwegnahme"' dieser Produktionen: Für jede Produktion mit einem der obigen $V$
auf der rechten Seite wird eine \textcolor{blue}{neue Produktion} ohne dieses $V$ hinzugefügt.
\end{enumerate}

\begin{exampleblock}{Umwandlungsbeispiel (Schritt 3 von 4)}
\ducttape{-0.25cm}
\begin{columns}[c]
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY\\
\textcolor{red}{X} &\rightarrow FB \mid Z \mid \textcolor{red}{\varepsilon}\\
\textcolor{red}{Y} &\rightarrow GY \mid \textcolor{red}{\varepsilon}\\
Z &\rightarrow X\\
F &\rightarrow AX\\
G &\rightarrow CC\\
A &\rightarrow a, B \rightarrow b, C \rightarrow c\\
\end{align*}
\end{column}
%
\
\begin{column}{0.05\textwidth}
$\Rightarrow$
\end{column}
%
\begin{column}{0.3\textwidth}
\begin{align*}
\textcolor{red}{\mathcal{S}} &\rightarrow XY \mid \textcolor{blue}{X} \mid  \textcolor{blue}{Y} \mid \textcolor{blue}{\varepsilon}\\
\textcolor{red}{X} &\rightarrow FB \mid Z \mid \textcolor{blue}{\msout{\varepsilon}}\\
\textcolor{red}{Y} &\rightarrow GY \mid \textcolor{blue}{G}\\
\textcolor{red}{Z} &\rightarrow X\mid \textcolor{blue}{\msout{\varepsilon}}\\
F &\rightarrow AX \mid \textcolor{blue}{A}\\
G &\rightarrow CC\\
A &\rightarrow a, B \rightarrow b, C \rightarrow c\\
\end{align*}
\end{column}
\end{columns}
\end{exampleblock}
\end{frame}



\frame{
\frametitle{Umwandlung in Chomsky-Normalform}
\begin{enumerate}
\setcounter{enumi}{3}
\item
Für Produktionen mit einer Variablen rechts werden Zyklen gesucht, 
für gefundene Zyklen werden alle Vorkommnisse aller Variablen des Zyklus durch einen Repräsentanten ausgetauscht. Danach werden triviale Produktionen entfernt.
\end{enumerate}

\begin{exampleblock}{Umwandlungsbeispiel (Schritt 4a von 4)}
\begin{columns}[c]
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY \mid X \mid Y \mid \varepsilon \\
\textcolor{red}{X} &\rightarrow FB \mid \textcolor{red}{Z} \\
Y &\rightarrow GY \mid G \\
\textcolor{red}{Z} &\rightarrow \textcolor{red}{X}\\
F &\rightarrow AX \mid A\\
G &\rightarrow CC\\
A &\rightarrow a, B \rightarrow b, C \rightarrow c\\
\end{align*}
\end{column}
%
\
\begin{column}{0.05\textwidth}
$\Rightarrow$
\end{column}
%
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY \mid X \mid Y \mid \varepsilon \\
\textcolor{blue}{X} &\rightarrow FB \mid \msout{\textcolor{blue}{X}} \\
Y &\rightarrow GY \mid G\\
\msout{\textcolor{blue}{X}} &\rightarrow \msout{\textcolor{blue}{X}}\\
F &\rightarrow AX\\
G &\rightarrow CC\\
A &\rightarrow a, B \rightarrow b, C \rightarrow c\\
\end{align*}
\end{column}
\end{columns}
\end{exampleblock}
}

\frame{
\frametitle{Umwandlung in Chomsky-Normalform}
\begin{enumerate}
\setcounter{enumi}{3}
\item
Alle Regeln, die rechts eine einzelne Variable haben, werden durch "`Vorziehen"' der Regeln eliminiert.

Außerdem wird ein neues Startsymbol eingeführt, falls eine Regel $\mathcal{S} \rightarrow \varepsilon$ existiert.
\end{enumerate}

\begin{exampleblock}{Umwandlungsbeispiel (Schritt 4b von 4)}
\ducttape{-0.4cm}
\begin{columns}[c]
\begin{column}{0.3\textwidth}
\begin{align*}
\mathcal{S} &\rightarrow XY \mid \textcolor{red}{X} \mid  \textcolor{red}{Y} \mid \textcolor{red}{\varepsilon}\\
X &\rightarrow FB\\
Y &\rightarrow GY \mid \textcolor{red}{G}\\
F &\rightarrow AX\\
G &\rightarrow CC\\
A &\rightarrow a\\
B &\rightarrow b\\
C &\rightarrow c\\
\end{align*}
\end{column}
%
\
\begin{column}{0.05\textwidth}
$\Rightarrow$
\end{column}
%
\begin{column}{0.3\textwidth}
\begin{align*}
\textcolor{blue}{\mathcal{S}} & \rightarrow \textcolor{blue}{\mathcal{S'} \mid \varepsilon} \\
\mathcal{S} &\rightarrow XY \mid \textcolor{blue}{FB} \mid \textcolor{blue}{GY} \mid \textcolor{blue}{CC}\\
X &\rightarrow FB \\
Y &\rightarrow GY \mid \textcolor{blue}{CC} \\
F &\rightarrow AX\\
G &\rightarrow CC\\
A &\rightarrow a\\
B &\rightarrow b\\
C &\rightarrow c\\
\end{align*}
\end{column}
\end{columns}
\end{exampleblock}
}

\begin{frame}
\frametitle{Aufgabe}
Sei $G=(\Sigma,V,S,R)$ die CH-2-Grammatik mit $\Sigma = \{a,b\}$, $V=\{A,B,C,D,E,S\}$ und der folgenden Regelmenge $R$:
\begin{eqnarray*}
S & \rightarrow & A \;|\; aAa  \;|\; bBb  \;|\; \varepsilon \\
A & \rightarrow & C \;|\; a \\
B & \rightarrow & C \;|\; b \\
C & \rightarrow & CDE \;|\; \varepsilon \\
D & \rightarrow & A \;|\; B \;|\; ab \\
E & \rightarrow & S
\end{eqnarray*}
Bestimme eine Grammatik $G'$ für $L(G)$ in Chomsky-Normalform.
\end{frame}

\section{CYK}
\subsection{Not CMYK!}

\frame{
\frametitle{CYK Überblick}
CYK ist ein Algorithmus, um das Wortproblem in CH-2 zu lösen. Um den Algorithmus anzuwenden, muss eine Grammatik in Chomsky-Normalform vorliegen.\\
Grundidee zur Überprüfung eines Wortes der Länge $n$:
\begin{itemize}
\item Wir betrachen $V_{i,j} = $ Menge der Nichtterminale, aus denen das Teilwort der Position $i$ bis $j$ abgeleitet werden kann
\item Die Frage, ob $V_{i,j}$ ableitbar ist, lässt sich entscheiden durch Betrachten aller möglichen $V_{i,k}$ und $V_{k+1,j}$
\item $V_{i,i}$ sind trivial
\item Bottom-up lässt sich dadurch $V_{1,n}$ berechnen
\item Ist $S \in V_{1,n}$, so lässt sich das Wort ableiten
\end{itemize}
}

\frame{
\frametitle{CYK}
Gegeben sei die Grammatik \textit{G} $= \mathcal{(T,V,}S\mathcal{,P) }$  mit den folgenden Produktionen aus $\mathcal{P}$:
\begin{align*}
S & \rightarrow AX \mid AB \\
X &\rightarrow SB \mid AB \\
A &\rightarrow a\\
B &\rightarrow b\\
\end{align*}
\begin{enumerate}
	\item Lässt sich der CYK-Algorithmus auf $G$ anwenden?
	\item Ist das Wort $aaabbb$ in der Sprache $\mathcal{L}(\textit{G})$?
\end{enumerate}
}
\section{Pumping Lemma und Ogdens Lemma}
\subsection{Pumping Lemma für kontextfreie Sprachen}
\begin{frame}
\frametitle{Pumping-Lemma für kontextfreie Sprachen}
\begin{exampleblock}{Lemma}
Für jede kontextfreie Sprache $L$ gibt es eine Konstante $n \in \mathbb{N}$,
so dass sich jedes Wort $z \in L$ mit $|z| \geq n$ so als
$$ z = uvwxy $$
schreiben lässt, dass
\begin{itemize}
\item $|vx| \geq 1$,
\item $|vwx| \leq n$ und
\item für alle $i \geq 0$ das Wort $uv^iwx^iy \in L$ ist.
\end{itemize}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Beweisidee}
\begin{itemize}
\item Jeder Knoten im Ableitungsbaum (wie wir ihn in CYK sehen) steht für ein Nichtterminalsymbol
\item Ab einer gewissen Höhe des Baumes (bzw. Länge des Wortes) muss ein Nichtterminal im Baum mehrmals in einer Reihe vorkommen
\item Man kann also aus einem Nichtterminalsymbol dasselbe Symbol wieder ableiten
\item Da das Wort durch jede Ableitung (außer zu Terminalsymbolen) länger wird, gibt es eine "`Schleife"' beim Ableiten
\item Diese Schleife kann man also "`pumpen"', also beliebig oft (oder auch gar nicht) durchlaufen
\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Beweisidee}
	\begin{figure}[H]
		\centering
		\includegraphics[scale=0.5]{images/pumping}
	\end{figure}
\end{frame}

\subsection{Ogdens Lemma}
\begin{frame}
\frametitle{Ogdens Lemma für kontextfreie Sprachen}
\begin{exampleblock}{Lemma}
Für jede kontextfreie Sprache $L$
gibt es eine Konstante $n \in \mathbb{N}$, so dass für jedes Wort $z \in L$ mit $|z| \geq n$ gilt:\\
Wenn wir in $z$ mindestens $n$ Buchstaben markieren, so lässt sich $z$ so als $z = uvwxy$ schreiben, dass
\begin{itemize}
\item von den mindestens $n$ markierten Buchstaben
\begin{itemize}
\item mindestens einer zu $vx$ gehört und
\item höchstens $n$ zu $vwx$ gehören und
\end{itemize}
\item für alle $i \geq 0$ das Wort $uv^iwx^iy \in L$ ist.
\end{itemize}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Zu Ogden und Pumping ...}
\begin{itemize}
\item Anwendung genau wie "`altes"' Pumping Lemma
\item Wird verwendet, um zu zeigen dass eine Sprache nicht kontextfrei ist
\item Dazu: Kontraposition bilden und folgern, dass Sprache nicht kontextfrei
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Aufgabe}

Zeige, dass folgende Sprachen nicht kontextfrei sind:

\begin{enumerate}
  \item $L_1 = \{w \in \{a, b, c\}^*: |w|_a = |w|_b = |w|_c\}$,
	wobei $|w|_x$ für die Häufigkeit des
	Buchstabens $x$	im Wort $w$ stehe.
  \item $L_2 = \{a^ib^ic^j \mid j \leq i\}$
  \item $L_3=\{a^ib^jc^id^j \mid i,j \geq 1 \}$

\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Aufgabe}
\begin{enumerate}
  \item 
        Zeige, dass die Sprache
	\begin{quote}
	  $L = \{a^j b^k c^l d^m \mid j=0 \vee k=l=m\}$
	\end{quote}
	die notwendige Bedingung des Pumping-Lemmas für Kontextfreiheit
	erfüllt.
  \item Zeige, dass $L$ nicht kontextfrei ist.
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Lösung zu 1.}

Setze $n := 1$, denn für jedes Wort $z \in L$ mit $\abs{w} \geq 1$ gilt:

\begin{description}
	\item[Fall $j = 0$:] Dann ist $z = b^kc^ld^m$ mit $k, l, m \in \N_0$. Zerlege $z = uvwxy$ mit $u, x, y = \varepsilon, \abs{v} = 1$, denn jedes $z'=uv^ixy^iz = v^iw$ ist in $L$, da keine $a$ darin vorkommen ($j=0$).
	\item[Fall $j \neq 0$:] Dann ist $z=a^jb^kc^kd^k$. Zerlege $z = uvwxy$ mit $u,w, x = \varepsilon, v = a \Rightarrow y = a^{j-1}b^kc^kd^k$. Dann ist für alle $i \in \N_0$ $uv^iwx^iy = a^{j+i}b^kc^kd^k \in L$.
\end{description}

\end{frame}

\begin{frame}
\frametitle{Lösung zu 2.}
Sei $L = \menge{a^ib^jc^kd^l}{i = 0 \vee j = k = l}$. Wir zeigen mit Ogdens Lemma, dass $L$ nicht kontextfrei ist. \micropause
Annahme: $L$ sei kontextfrei. Für gegebenes $n$ müsste Ogdens Lemma also für jedes Wort mit $n$ markierten Buchstaben erfüllt sein. \micropause
Betrachte aber $z = ab^nc^nd^n \in L$ und markiere $b^n$. \micropause
Zu $vx$ muss also immer ein $b$ gehören und in $vwx$ dürfen höchsten $n$ markierte Buchstaben vorkommen. Offensichtlich dürfen in $v$ und $x$ jeweils nur eine Art von Symbol vorkommen. Da aber in $v$ oder $x$ mindestens ein $b$ vorkommen muss, und die Anzahl der $b$ und $c$ und $d$ gleich bleiben muss, ist das Lemma nicht erfüllt. Daher kann $L$ nicht kontextfrei sein.
\end{frame}

\section{Schluss}
\subsection{Aus!}
\begin{frame}
\frametitle{Bis zum nächsten Mal!}
\only<1>{
	\begin{figure}[H]
		\includegraphics[height= 0.8\textheight]{images/grandma}

        \textit{\scriptsize{http://twitter.com/herpderpedia}}
	\end{figure}
}

\only<2>{
	\begin{figure}[H]
		\includegraphics[width= \textwidth]{images/xkcd_416}
		
		\textit{\scriptsize{I hear this is an option in the latest Ubuntu release.}}
		
	\end{figure}
}
\end{frame}

\include{includes/common_end}