--- a/notes/tex/ue03_notes.tex	Thu Jul 11 21:57:50 2013 +0200
+++ b/notes/tex/ue03_notes.tex	Thu Jul 11 22:06:26 2013 +0200
@@ -1,185 +1,16 @@
 \input{preamble.tex}
+\input{frames.tex}
 
 \title{Übung 3: Ardens- und Pumpinglemma}
 \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{Nochmal Reguläre Ausdrücke}
-    \setbeamercovered{dynamic}
-
-    \begin{theorem}
-        Die regulären Ausdrücke $\mathfrak{R}$ über einem Alphabet $\Sigma$ bilden mit Konkatenation $\circ$ und Veroderung $\mid$ einen \alert{Halbring} $\langle \mathfrak{R}, \mid, \circ, \emptyset, \epsilon \rangle$.
-
-        \begin{itemize}
-            \item \alert{Assoziative} Operationen
-            \item Veroderung \alert{kommutativ}
-            \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$
-            \item $\emptyset$ \alert{neutral} bezüglich Oder
-            \item $\epsilon$ \alert{neutral} bezüglich Konkatenation
-        \end{itemize}
-    \end{theorem}
-
-    \begin{example}
-        \[
-            1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi
-        \]
-    \end{example}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Ardens Lemma}
-    \setbeamercovered{dynamic}
-
-    \begin{theorem}[Ardens Lemma]
-        Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt
-        \[
-            X = AX \cup B \Longrightarrow X = A^* B
-        \]
-        Speziell gilt für reguläre Ausdrücke
-        \[
-            X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta
-        \]
-    \end{theorem}
-
-
-    \begin{example}
-        \[
-            \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi
-        \]
-    \end{example}
-\end{frame}
-
-\begin{frame}
-    \frametitle{NFA $\rightarrow$ RE}
-    \setbeamercovered{dynamic}
-
-    \begin{block}{Idee}
-        Erzeuge ein Gleichungssystem aus allen Zuständen.
-        \begin{enumerate}
-            \item<1,2-> Ausdruck für jeden Zustand
-            \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma
-        \end{enumerate}
-    \end{block}
-    \begin{columns}<2->
-        \begin{column}[b]{.65\textwidth}
-            \begin{align*}
-                X_0 &\equiv 1X_0 \mid 0X_1 \\
-                &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\
-                &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\
-                &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\
-                \\
-                X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\
-                &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\
-                &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}}
-            \end{align*}
-        \end{column}
-        \begin{column}[t]{.35\textwidth}
-            \begin{tikzpicture}[automaton]
-                \node[state, initial] (q0) {$q_0$};
-                \node[state, accepting] (q1) [below of=q0] {$q_1$};
-
-                \draw[->] (q0) edge [bend right] node [left] {$0$} (q1);
-                \draw[->] (q1) edge [bend right] node [right] {$1$} (q0);
-                \draw[->] (q0) edge [loop right] node {$1$} (q0);
-                \draw[->] (q1) edge [loop right] node {$0$} (q1);
-            \end{tikzpicture}
-        \end{column}
-    \end{columns}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Pumping Lemma}
-    \setbeamercovered{dynamic}
-
-    \begin{theorem}[Pumping Lemma für reguläre Sprachen]
-        Sei $R \subseteq \Sigma^*$ regulär. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass
-        \begin{itemize}
-            \item $v \neq \epsilon$
-            \item $|uv| \alert{\leq n}$
-            \item $\forall i \alert{\geq 0}. uv^iw \in R$
-        \end{itemize}
-    \end{theorem}
-
-    \vfill
-
-    \begin{center}
-        \begin{tikzpicture}[automaton]
-            \node[state, initial] (q0) {};
-            \node[state, fill=tumred!20] (q1) [right of=q0] {};
-            \node[state, accepting] (q2) [right of=q1] {};
-
-
-            \draw[->, densely dashed] (q0) edge node {$u$} (q1);
-            \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1);
-            \draw[->, densely dashed] (q1) edge node {$w$} (q2);
-        \end{tikzpicture}
-    \end{center}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Nichtregularität beweisen}
-    \setbeamercovered{dynamic}
-
-    \begin{block}{Idee}
-        Gegenbeispiel fürs Pumpinglemma suchen.
-        \[
-            \alert{\forall} n \in \N_0 \alert{\exists} z \in L. |z| \geq n \ \alert{\forall} u,v,w. \ z = uvw \ \text{\alert{nicht} pumpbar}
-        \]
-    \end{block}
-
-    \vfill
-
-    \begin{example}<2->
-        Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär?
-        \begin{enumerate}
-            \item \alert{Sei $n$} PL-Zahl
-            \item \alert{Wähle} $\alert{z} = a^nb^n$
-            \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$
-            \item Dann ist $uv^0w \not \in L$
-            \item Damit ist L \alert{nicht} regulär.
-        \end{enumerate}
-    \end{example}
-\end{frame}
-
-\begin{frame}
-    \frametitle{Reguläre Sprachen}
-    \setbeamercovered{dynamic}
-
-    \begin{center}
-        \begin{tikzpicture}[node distance=2cm]
-            \node (nfa) {NFA};
-            \node (dfa) [left of=nfa] {DFA};
-            \node (enfa) [right of=nfa] {$\epsilon$-NFA};
-            \node (re) [below of=nfa] {RE};
-
-            \draw [every edge] (nfa) -- (dfa);
-            \draw [every edge] (enfa) -- (nfa);
-            \draw [every edge] (dfa) -- (re);
-            \draw [every edge] (nfa) -- (re);
-            \draw [every edge] (re) -- (enfa);
-        \end{tikzpicture}
-    \end{center}
-
-    \vfill
-    \pause
-
-    \begin{theorem}
-        Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
-        \vspace{1em}
-        \begin{description}
-            \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
-            \item[Leerheitsproblem] Ist $L(D) = \emptyset$?
-            \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
-            \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$?
-        \end{description}
-    \end{theorem}
-\end{frame}
-
+\showUnit{titel}
+\showUnit{regexrechnen}
+\showUnit{arden}
+\showUnit{nfazure}
+\showUnit{rpl}
+\showUnit{rplanwenden}
+\showUnit{regulaeresprachen}
 \end{document}