--- a/notes/tex/ue04_notes.tex	Mon Jun 10 20:06:43 2013 +0200
+++ b/notes/tex/ue04_notes.tex	Mon Jun 10 23:21:11 2013 +0200
@@ -148,7 +148,7 @@
                 \draw<-5>[->] (q1) edge node {$a,b$} (q3);
                 \draw<-5>[->] (q2) edge node {$a,b$} (q3);
                 \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3);
-                
+
                 \draw<6>[->] (q12) edge node {$a,b$} (q3);
                 \draw<6>[->] (q0) edge node {$a,b$} (q12);
             \end{tikzpicture}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue07_notes.tex	Mon Jun 10 23:21:11 2013 +0200
@@ -0,0 +1,205 @@
+\documentclass[compress, german, t]{beamer}
+
+\usepackage[ngerman,english]{babel}
+\uselanguage{German}
+\languagepath{German}
+
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+
+\usepackage{helvet}
+\usepackage{url}
+\usepackage{listings}
+\usepackage{xcolor}
+\usepackage{tikz}
+\usepackage{pgfplots}
+\usetikzlibrary{automata}
+\usetikzlibrary{calc}
+\usetikzlibrary{shapes.geometric}
+\usetikzlibrary{positioning}
+\usepackage{tabu}
+
+\usepackage{beamerthemeLEA2}
+
+\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
+\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
+\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
+\newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
+\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
+\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}
+
+\tikzstyle{every edge} = [draw,very thick,->,>=latex]
+\tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
+\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
+\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE]
+
+\title{Übung 7: CYK und Kellerautomaten}
+\subtitle{Theoretische Informatik Sommersemester 2013}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+
+\begin{frame}
+    \titlepage
+\end{frame}
+
+\begin{frame}
+    \frametitle{CYK}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Cocke-Younger-Kasami-Algorithmus]
+        Der \alert{CYK-Algorithmus} entscheidet das Wortproblem für kontextfreie Grammatiken in Chomsky-Normalform in $\Oh(n^3)$. \\
+        Gegeben eine \alert{Grammatik} $G = (V, \Sigma, P, S)$ in CNF und ein \alert{Wort} $w = a_1 \ldots a_n \in \Sigma^*$.
+        Mit \[ V_{ij} := \left\{ A \in V \mid A \rightarrow_G^* \alert{a_i \ldots a_j} \right\}\]
+        ist \[ w \in L(G) \Leftrightarrow S \in V_{\alert{1n}} \]
+    \end{definition}
+
+    \begin{align*}
+        V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\
+        V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\}
+    \end{align*}
+
+\end{frame}
+
+\begin{frame}
+    \frametitle{CYK}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Idee}
+        Kombiniere \alert{Teilwörter} zum ganzen Wort, wenn möglich.
+        \begin{enumerate}
+            \item Initialisiere mit den \alert{$V_{ii}$}.
+            \item<3-5> Befülle die Tabelle von unten nach oben.
+        \end{enumerate}
+    \end{block}
+
+    \[ S \rightarrow AB \mid BC, \quad A \rightarrow BA \mid a, \quad B \rightarrow CC \mid b, \quad C \rightarrow AB \mid a \]
+    \begin{center}
+        \extrarowsep=5pt
+        \begin{tabu}to .8\textwidth{r|X[c]|X[c]|X[c]|X[c]|}
+            \tabucline{2-2}
+            4 & \alt<-4>{}{$S,\ldots$} \\ \tabucline{2-3}
+            3 & \alt<-3>{}{$\emptyset$} & \alt<-3>{}{$S, A, C$} \\ \tabucline{2-4}
+            2 & \alt<-2>{}{$A$} & \alt<-2>{}{$B$} & \alt<-2>{}{$B$} \\ \tabucline{2-5}
+            1 & \alt<-1>{}{$B$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} & \alt<1>{}{$A,C$} \\ \tabucline{2-5}
+            \multicolumn{1}{r}{} & \multicolumn{1}{c}{\alert{b}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} & \multicolumn{1}{c}{\alert{a}} \\
+        \end{tabu}
+    \end{center}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Kellerautomaten}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Kellerautomat]
+        Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
+        \begin{itemize}
+            \item endlichen Menge von \alert{Zuständen} $Q$
+            \item endlichen \alert{Eingabealphabet} $\Sigma$
+            \item endlichen \alert{Kelleralphabet} $\Gamma$
+            \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$
+            \item \alert{Startzustand} $q_0 \in Q$
+            \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$
+            \item Menge von \alert{Endzuständen} $F \subseteq Q$
+        \end{itemize}
+    \end{definition}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Kellerautomaten}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Kellerautomat]
+        Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
+        \begin{itemize}
+            \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Akzeptanz]
+        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit Endzustand} gdw
+        \[ \exists \alert{f \in F}, \gamma \in \Gamma^*.(q_0, w, Z_0) \rightarrow_P^* (\alert{f}, \epsilon, \gamma) \]
+        Ein PDA $P$ akzeptiert $w \in \Sigma^*$ \alert{mit leerem Keller} gdw
+        \[ \exists q \in Q.(q_0, w, Z_0) \rightarrow_P^* (q, \epsilon, \alert{\epsilon}) \]
+    \end{definition}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Kellerautomaten}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Kellerautomat]
+        Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
+        \begin{itemize}
+            \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \begin{example}[]
+        PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$.
+
+        \centering
+        \begin{tikzpicture}[automaton]
+
+            \node[state, initial] (q0) {$q_0$};
+            \node[state] (q1) [right of = q0] {$q_1$};
+
+            \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1);
+            \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1);
+
+            \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0);
+            \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0);
+
+            \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1);
+            \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1);
+        \end{tikzpicture}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Kontextfreie Sprachen}
+    \setbeamercovered{dynamic}
+
+    \begin{center}
+        \begin{tikzpicture}[node distance=3cm]
+            \node (CFG) {CFG};
+            \node (CNF) [right of = CFG] {CNF};
+            \node (PDAe) [right of = CNF] {PDA$_\epsilon$};
+            \node (PDAf) [right of = PDAe] {PDA$_F$};
+
+            \draw [every edge, <->] (CFG) -- (CNF);
+            \draw [every edge, <->] (CNF) -- (PDAe);
+            \draw [every edge, <->] (PDAe) -- (PDAf);
+        \end{tikzpicture}
+    \end{center}
+
+    \pause
+    \vfill
+
+    \begin{itemize}
+        \item \alert{Abschlusseigenschaften}
+    \end{itemize}
+    \begin{table}
+        \begin{tabu}to \textwidth{X[c]|ccccc}
+            & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
+            REG & ja & ja & ja & ja & ja\\
+            CFL & nein & ja & nein & ja & ja 
+        \end{tabu}
+    \end{table}
+    \begin{itemize}
+        \item \alert{Entscheidbarkeit}
+    \end{itemize}
+    \begin{table}
+        \begin{tabu}to \textwidth{X[c]|cccc}
+            & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
+            DFA & $\Oh(n)$ & ja & ja & ja \\
+            CFG & $\Oh(n^3)$ & ja & nein & nein
+        \end{tabu}
+    \end{table}
+\end{frame}
+
+\end{document}

Binary file notes/ue07_notes.pdf has changed