--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue04_notes.tex	Mon May 13 23:19:33 2013 +0200
@@ -0,0 +1,159 @@
+\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 4: Minimale DFAs}
+\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{Äquivalenzen}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Äquivalente Worte]
+        Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$:
+        \[
+            u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right)
+        \]
+    \end{definition}
+
+    \vfill
+
+    \pause
+
+    \begin{definition}[Äquivalente Zustände]
+        Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren.
+
+        \[
+            p \alert{\equiv_A} q \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{\hat{\delta}(p, w)} \in F \Leftrightarrow \alert{\hat{\delta}(q, w)} \in F \right)
+        \]
+    \end{definition}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Unterscheidbare Zustände}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Unterscheidbarkeit]
+        Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
+        \[
+            p \alert{\not\equiv_A} q \Longleftrightarrow \left( \exists w \in \Sigma^*. \hat{\delta}(p, w) \alert{\in} F \wedge \hat{\delta}(q, w) \alert{\not\in} F \right)
+        \]
+    \end{definition}
+
+    \begin{theorem}
+        Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$.
+    \end{theorem}
+
+    \pause
+
+    \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm]
+        \node[state, initial] (q0) {$q_0$};
+        \node[state] (q1) [right of = q0] {$q_1$};
+        \node[state] (q2) [right of = q1] {$q_2$};
+        \node[state, accepting] (q3) [right of = q2] {$q_3$};
+
+        \draw[->] (q0) edge node {$a$} (q1);
+        \draw[->] (q0) edge [bend left] node {$b$} (q2);
+        \draw[->] (q1) edge node {$a$} (q2);
+        \draw[->] (q1) edge [bend right] node {$b$} (q3);
+        \draw[->] (q2) edge node {$a,b$} (q3);
+        \draw[->] (q3) edge [loop right] node {$a,b$} (q3);
+
+        \node<3>[state, fill=tumred!35] () at (q2) {$q_2$};
+        \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$};
+
+        \node<4>[state, fill=tumred!35] () at (q0) {$q_0$};
+        \node<4>[state, fill=tumred!35] () at (q1) {$q_1$};
+        \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2);
+        \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3);
+    \end{tikzpicture}
+\end{frame}
+
+\begin{frame}[t]
+    \frametitle{DFA minimieren}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Idee}
+        Erzeuge den \alert{Quotientenautomaten}.
+        \begin{enumerate}
+            \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände
+            \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände
+            \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände
+        \end{enumerate}
+    \end{block}
+
+    \vfill
+
+    \begin{columns}[c]<2->
+        \begin{column}{.5\textwidth}<3->
+            \begin{center}
+                \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X}
+                    \multicolumn{2}{l}{0} \\ \tabucline{1-1}
+                    \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2}
+                    \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} &  & \multicolumn{2}{l}{2} \\ \tabucline{1-3}
+                    \alt<-3>{}{\textcolor{tumred}{$\times$}} &  \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3}
+                \end{tabu}
+            \end{center}
+        \end{column}
+        \begin{column}{.5\textwidth}
+            \begin{tikzpicture}[automaton, node distance=2.5cm]
+                \useasboundingbox (-0.5, -0.5) rectangle (2, -2);
+
+                \node[state, initial] (q0) {$q_0$};
+                \node<-5>[state] (q1) [right of = q0] {$q_1$};
+                \node<-5>[state] (q2) [below of = q0] {$q_2$};
+                \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$};
+                \node[state, accepting] (q3) [right of = q2] {$q_3$};
+
+                \draw<-5>[->] (q0) edge node {$a$} (q1);
+                \draw<-5>[->] (q0) edge node {$b$} (q2);
+                \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}
+        \end{column}
+    \end{columns}
+\end{frame}
+
+\end{document}

Binary file notes/ue04_notes.pdf has changed