tutorium3.tex

\include{includes/common_start}
\include{includes/tutBlatt_methods}
\tutnr{3}

\section{Pumping Lemma}
\subsection{Pumping Lemma}
\begin{frame}
	\frametitle{Pumping Lemma}
	
%\begin{exampleblock}{Pumping Lemma}
Sei $L$ eine reguläre Sprache. Dann existiert eine Zahl $n \in \mathbb{N}$, sodass für jedes Wort $w \in L$ mit $\left|w \right| > n$ eine Darstellung $$w = uvx$$ existiert, so dass folgende Eigenschaften erfüllt sind:

\begin{enumerate}
\item $v \neq \lambda$
\item $\left|uv\right| \leq n$ 
\item Für alle $i \in \mathbb{N}_0$ gilt: $uv^ix \in L$
\end{enumerate}
%\end{exampleblock}

\begin{center}
\includegraphics[width=0.55\textwidth]{images/Q116}
\end{center}

\end{frame}

\subsection{Aufgabe 1}
\begin{frame}
	\frametitle{Aufgabe 1}
	Gegeben sei die Sprache $\mathcal{L} = \{w \in \{a,b\}^* \; | \; w \;
	\mbox{enth"alt gleich viele $a$ wie $b$}\}$.
	\begin{enumerate}
		\item Wie lautet das Pumping Lemma? Was genau muss man zeigen, falls man die
		Kontraposition des\\
		Pumping Lemmas verwenden will?
		\item Zeigen Sie mit Hilfe des Pumping Lemmas, dass L nicht regul"ar ist!
		\item Zeigen Sie mit Hilfe des Pumping Lemmas, dass die Sprache $\mathcal{L}' =
		\{a^p\; | \; p \; \mbox{Primzahl}\}$ nicht regul"ar ist.
		\item Betrachten Sie nun die Sprache $\mathcal{L}'' = \{a,aab,aaab\}$! Ist diese
		regul"ar? Falls ja, geben Sie einen endlichen\\
		Automaten an, der diese Sprache akzeptiert! Kann man mit dem Pumping Lemma zeigen,
		dass die\\
		Sprache regul"ar ist?
	\end{enumerate}
\end{frame}

\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 \lambda $$
\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 \lambda\\
Y &\rightarrow \textcolor{red}{cc}Y \mid \lambda\\
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 \lambda\\
Y &\rightarrow \textcolor{blue}{CC}Y \mid \lambda\\
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 \lambda \\
Y &\rightarrow \textcolor{red}{CCY} \mid \lambda \\
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 \lambda \\
Y &\rightarrow \textcolor{blue}{GY} \mid \lambda \\
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}{\lambda}$
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}{\lambda}\\
\textcolor{red}{Y} &\rightarrow GY \mid \textcolor{red}{\lambda}\\
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}{\lambda}\\
\textcolor{red}{X} &\rightarrow FB \mid Z \mid \textcolor{blue}{\msout{\lambda}}\\
\textcolor{red}{Y} &\rightarrow GY \mid \textcolor{blue}{G}\mid \textcolor{blue}{\msout{\lambda}}\\
\textcolor{red}{Z} &\rightarrow X\\
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 \lambda \\
\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 \lambda \\
\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 \lambda$ 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}{\lambda}\\
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 \lambda} \\
\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}
}

\subsection{Aufgabe 2a}
\begin{frame}
	\frametitle{Aufgabe 2}
	Gegeben sei die folgende Grammatik: $\mathcal{G} = (\mathcal{T},\mathcal{V},S,
	\mathcal{P})$ mit\\
	$\mathcal{T} := \{a,b,c,d\}$, $\mathcal{V} := \{S,A,D,M\}$, $\mathcal{P} := \{
	S \rightarrow AMD \; | \; M, A \rightarrow AA \; | \; a, D \rightarrow DD \; | \; d,
	M \rightarrow bMc \; | \; \lambda\}$
	\begin{enumerate}
		\item Geben Sie die erzeugte Sprache an!
		\item Wandeln Sie die gegebene kontextfreie Grammatik $\mathcal{G}$ in eine
		"aquivalente kontextfreie Grammatik $\mathcal{G}'$ in\\
		Chomsky-Normalform um, indem sie jeden Schritt durch eine neue Grammatik beschreiben!
	\end{enumerate}
\end{frame}

\section{CYK-Algorithmus}
\subsection{CYK-Algorithmus}
\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 Beispiel}
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}
}

\subsection{Aufgabe 2b}
\begin{frame}
	\frametitle{Aufgabe 2 Fortsetzung}
	Gegeben sei die folgende Grammatik: $\mathcal{G} = (\mathcal{T},\mathcal{V},S,
	\mathcal{P})$ mit\\
	$\mathcal{T} := \{a,b,c,d\}$, $\mathcal{V} := \{S,A,D,M\}$, $\mathcal{P} := \{
	S \rightarrow AMD \; | \; M, A \rightarrow AA \; | \; a, D \rightarrow DD \; | \; d,
	M \rightarrow bMc \; | \; \lambda\}$
	\begin{enumerate}
		\item Geben Sie die erzeugte Sprache an!
		\item Wandeln Sie die gegebene kontextfreie Grammatik $\mathcal{G}$ in eine
		"aquivalente kontextfreie Grammatik $\mathcal{G}'$ in\\
		Chomsky-Normalform um, indem sie jeden Schritt durch eine neue Grammatik beschreiben!
		\item Zeigen oder widerlegen Sie mit Hilfe des CYK-Algorithmus, ob die folgenden
		W"orter in der Sprache $\mathcal{L}$\\
		liegen, die durch die Grammatik $\mathcal{G}$ erzeugt wird!
		\begin{enumerate}
			\item $aabbccdd$
			\item $abbcc$
			\item $abcdd$
		\end{enumerate}
	\end{enumerate}
\end{frame}

\section{Kellerautomaten}
\subsection{Kellerautomaten}
\begin{frame}
	\frametitle{Definition Kellerautomaten}
	Ein (nichtdeterministischer) \textbf{Kellerautomat} (NPDA bzw PDA, Pushdown Automaton) besteht aus $(Q, \Sigma, \Gamma, q_0, Z_0,\delta, F)$, wobei
	\begin{itemize}
		\item $Q$ endliche Zustandsmenge
		\item $\Sigma$ endliches Eingabealphabet
		\item $\Gamma$ endliches Stack-Alphabet
		\item $q_0 \in Q$ Anfangszustand
		\item $Z_0 \in \Gamma$ Initialisierung des Stacks
		\item $\delta : Q \times ( \Sigma \cup \{\lambda\}) \times \Gamma \rightarrow 2^{Q \times \Gamma^*}$
		\begin{itemize}
			\item $\delta(q, a, Z) \subseteq \{(q,\gamma) : q \in Q, \gamma \in \Gamma^*\}$
			\item $\delta(q, \lambda, Z) \subseteq \{(q,\gamma) : q \in Q, \gamma \in \Gamma^*\}$
		\end{itemize}
		\item $F \subseteq Q$ Menge der akzeptierenden Endzustände, $F=\emptyset$ ist möglich.
		
		\vspace{-4cm}\raggedleft{\includegraphics[width=0.5\textwidth]{images/PDA.png}}
	\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Zu Kellerautomaten}
\begin{itemize}
\item Akzeptieren nach Eingabeende, wenn \begin{itemize}
	\item der Stack leer ist \emph{oder}
	\item der Automat in einen akzeptierenden Zustand kommt.
\end{itemize}
\item Sind im Allgemeinen nichtdeterministisch
\item Man kann Endzustände auch aus der Definition weglassen und alternativ verlangen, dass der Automat genau bei leerem Keller akzeptiert.
\item Man kann sogar alle Zustände bis auf einen weglassen und alles in die Kellerbelegung kodieren
\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Beispiel}
	$M = (Q, \Sigma, \Gamma, q_0, Z_0, \delta, F)$
	\begin{itemize}
		\item $Q = \{q_0, q_1, q_2\}$
		\item $\Sigma = \{a,b\}$
		\item $\Gamma = \{\#,X\}$
		\item $Z_0 = \#$
		\item $F = \{q_2\}$
	\end{itemize}
	\begin{figure}
		\begin{tikzpicture}[node distance=2.5cm,shorten >=1pt,auto]
			\node[state,initial]   (q_0)                {$q_0$};
			\node[state]           (q_1) [right of=q_0] {$q_1$};
			\node[state,accepting] (q_2) [right of=q_1] {$q_2$};
			\path[->]	(q_0) 	edge 			node {$(b,X,\lambda)$}				(q_1)
			edge [loop above]	node {${(a,X,XX)} \atop {(a,\#,X\#)}$}	 	()
			(q_1)	edge			node {$(\lambda,\#,\lambda)$}			(q_2)
			edge [loop above]	node {$(b,X,\lambda)$}				();
		\end{tikzpicture}
	\end{figure}
	\begin{itemize}
		\item Welche Sprache akzeptiert dieser Automat?
	\end{itemize}
\end{frame}

\subsection{Aufgabe 3}
\begin{frame}
	\frametitle{Aufgabe 3}
	Gegeben sei folgende Sprache f"ur das Alphabet $\Sigma = \{a,b,c\}$:
	\begin{multline*}
		\mathcal{L} = \{w_1w_2 \in \Sigma^* \; | \; w_1 \in \{a,b\}^*,w_2 \in \{b,c\}^*,\\
		\#_a w_1 + \#_b w_1 = \#_b w_2 + \#_c w_2\}
	\end{multline*}
	Hier gibt $\#_x w$ die H"aufigkeit des Vorkommens eines Zeichens $x \in \Sigma$ in
	einem Wort $w \in \Sigma^*$ an.
	\begin{enumerate}
		\item Zeigen Sie, dass $\mathcal{L}$ nicht regul"ar ist!
		\item Geben Sie eine Chomsky-2-Grammatik an, die genau die Sprache $\mathcal{L}$
		erzeugt!
		\item Geben Sie einen Kellerautomaten $\mathcal{M}$ an, der genau die Sprache
		$\mathcal{L}$ erkennt! Zeichnen Sie den\\
		Zustands"ubergangsgraphen f"ur $\mathcal{M}$!
	\end{enumerate}
\end{frame}

\section{Schluss}
\subsection{Schluss}

\begin{frame}
\frametitle{Bis zum nächsten Mal!}
\begin{center}
  \includegraphics[width=1.5 \textheight]{images/schrodinger.jpg}
\end{center}
\end{frame}

\include{includes/common_end}