--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue03_notes.tex	Mon May 06 23:42:11 2013 +0200
@@ -0,0 +1,228 @@
+\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 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}[c]
+    \frametitle{Feedback}
+    \setbeamercovered{dynamic}
+    \begin{itemize}
+        \item Hausaufgaben
+        \item Übungsniveau
+        \item Links
+    \end{itemize}
+\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 = AB \cup X \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 reguläre Sprache $D$ 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}
+
+\end{document}

Binary file notes/ue03_notes.pdf has changed

Binary file ue03.pdf has changed

Binary file ue04.pdf has changed