--- a/notes/tex/automatons.tex	Thu Apr 24 09:04:24 2014 +0200
+++ b/notes/tex/automatons.tex	Sat Apr 26 17:50:08 2014 +0200
@@ -27,18 +27,17 @@
     \frametitle{DFA}
 
     \begin{definition}[Deterministischer endlicher Automat]
-        Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
+        Ein \structure{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
         \begin{itemize}
-            \item endlichen Menge von \alert{Zuständen} $Q$
-            \item endlichen \alert{Eingabealphabet} $\Sigma$
-            \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
-            \item \alert{Startzustand} $q_0 \in Q$
-            \item Menge von \alert{Endzuständen} $F \subseteq Q$
+            \item endlichen Menge von \structure{Zuständen} $Q$
+            \item endlichen \structure{Eingabealphabet} $\Sigma$
+            \item totalen \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
+            \item \structure{Startzustand} $q_0 \in Q$
+            \item Menge von \structure{Endzuständen} $F \subseteq Q$
         \end{itemize}
     \end{definition}
 
     \vfill
-    \pause
 
     \begin{center}
         \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
@@ -61,15 +60,14 @@
 \begin{frame}
     \frametitle{NFA}
     \begin{definition}[Nicht-Deterministischer endlicher Automat]
-        Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
+        Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
         \begin{itemize}
             \item $Q, \Sigma, q_0, F$ wie ein DFA
-            \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$
         \end{itemize}
     \end{definition}
 
     \vfill
-    \pause
 
     \begin{center}
         \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
@@ -82,15 +80,14 @@
 \begin{frame}
     \frametitle{$\epsilon$-NFA}
     \begin{definition}[NFA mit $\epsilon$-Übergängen]
-        Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
+        Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
         \begin{itemize}
             \item $Q, \Sigma, q_0, F$ wie ein DFA
-            \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$
+            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$
         \end{itemize}
     \end{definition}
 
     \vfill
-    \pause
 
     \begin{center}
         \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]
@@ -329,17 +326,23 @@
     \frametitle{NFA $\rightarrow$ DFA}
     \setbeamercovered{dynamic}
 
-    \begin{block}{Idee (Potenzmengenkonstruktion)}
-        Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}.
+    \begin{block}{Potenzmengenkonstruktion}
+        Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt.
+        Gegeben ein NFA $(Q, \Sigma, \delta, q_0, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}.
 
         \begin{itemize}
-            \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\
-                \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\]
-            \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$
+            \item Starte in $\left\{ q_0 \right\}$
+            \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
+                \begin{align}
+                    \overline{\delta}: \alert{\powerset{Q}} \times \Sigma &\to \powerset{Q} \\
+                    (S, a) &\mapsto \bigcup_{q \in S} \delta(q, a)
+                \end{align}
+            \item $S$ ist Endzustand wenn $F \cap S \neq \emptyset$
         \end{itemize}
     \end{block}
 
     \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
+        \tikzstyle{every state}=[minimum width=1cm, pretty]
         \useasboundingbox (-1.4,2) rectangle (9, -2);
 
         \node[state, initial] (q0) {$q_0$};

--- a/notes/tex/grammars.tex	Thu Apr 24 09:04:24 2014 +0200
+++ b/notes/tex/grammars.tex	Sat Apr 26 17:50:08 2014 +0200
@@ -131,6 +131,29 @@
 \end{frame}
 }
 
+\defineUnit{eindeutigkeit}{%
+\begin{frame}
+    \frametitle{Eindeutigkeit}
+
+    \begin{definition}[Linksableitung]
+        Eine Ableitung
+        \begin{align}
+            S \to^* x\alert{\alpha}z \to x\alert{\beta}z \to^* w
+        \end{align}
+        heißt \structure{Linksableitung}, wenn für jede Anwendung jeder Produktion $\alert{\alpha \to \beta}$ gilt, dass sich keine Regel in einem echten Präfix von $\structure{x\alpha}$ anwenden lässt.
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Eindeutigkeit]
+        \begin{itemize}
+            \item Eine Grammatik heißt \structure{eindeutig}, wenn es für jedes Wort genau eine Linksableitung gibt.
+            \item Eine Sprache heißt \structure{eindeutig}, wenn es für sie eine eindeutige Grammatik gibt.
+        \end{itemize}
+    \end{definition}
+\end{frame}
+}
+
 \defineUnit{cnf}{%
 \begin{frame}
     \frametitle{CNF}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue02_notes.tex	Sat Apr 26 17:50:08 2014 +0200
@@ -0,0 +1,16 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 2: Eindeutigkeit und Automaten}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{eindeutigkeit}
+\showUnit{dfa}
+\showUnit{nfa}
+\showUnit{enfa}
+\showUnit{endlicheautomaten}
+\showUnit{nfazudfa}
+\end{document}

Binary file notes/ue02_notes.pdf has changed

Binary file ue02.pdf has changed