changeset 12:11723d02ee58

use newer definitions
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 28 Apr 2014 12:27:03 +0200
parents de844d67518b
children 834da46b1edb
files notes/tex/automatons.tex notes/tex/ue02_notes.tex notes/ue02_notes.pdf
diffstat 3 files changed, 10 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- a/notes/tex/automatons.tex	Sat Apr 26 21:10:36 2014 +0200
+++ b/notes/tex/automatons.tex	Mon Apr 28 12:27:03 2014 +0200
@@ -60,9 +60,10 @@
 \begin{frame}
     \frametitle{NFA}
     \begin{definition}[Nicht-Deterministischer endlicher Automat]
-        Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
+        Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
         \begin{itemize}
-            \item $Q, \Sigma, q_0, F$ wie ein DFA
+            \item $Q, \Sigma, F$ wie ein DFA
+            \item Menge von \structure{Startzuständen} $S \subseteq F$
             \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
         \end{itemize}
     \end{definition}
@@ -80,9 +81,10 @@
 \begin{frame}
     \frametitle{$\epsilon$-NFA}
     \begin{definition}[NFA mit $\epsilon$-Übergängen]
-        Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
+        Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
         \begin{itemize}
-            \item $Q, \Sigma, q_0, F$ wie ein DFA
+            \item $Q, \Sigma, F$ wie ein DFA
+            \item Menge von \structure{Startzuständen} $S \subseteq F$
             \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$
         \end{itemize}
     \end{definition}
@@ -328,16 +330,16 @@
 
     \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}$}.
+        Gegeben ein NFA $(Q, \Sigma, \delta, S, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}.
 
         \begin{itemize}
-            \item Starte in $\left\{ q_0 \right\}$
+            \item Starte in $\left\{ S \right\}$
             \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
                 \begin{align}
                     \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\
-                    (S, a) &\mapsto \bigcup_{q \in S} \delta(q, a)
+                    (M, a) &\mapsto \bigcup_{q \in M} \delta(q, a)
                 \end{align}
-            \item $S$ ist Endzustand wenn $F \cap S \neq \emptyset$
+            \item $M$ ist Endzustand wenn $F \cap M \neq \emptyset$
         \end{itemize}
     \end{block}
 
--- a/notes/tex/ue02_notes.tex	Sat Apr 26 21:10:36 2014 +0200
+++ b/notes/tex/ue02_notes.tex	Mon Apr 28 12:27:03 2014 +0200
@@ -11,6 +11,5 @@
 \showUnit{dfa}
 \showUnit{nfa}
 \showUnit{enfa}
-\showUnit{endlicheautomaten}
 \showUnit{nfazudfa}
 \end{document}
Binary file notes/ue02_notes.pdf has changed