Mercurial > 14ss.theoinf

comparison notes/tex/automatons.tex @ 12:11723d02ee58

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
use newer definitions
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 28 Apr 2014 12:27:03 +0200
parents de844d67518b
children 834da46b1edb
comparison
equal deleted inserted replaced
11:de844d67518b 12:11723d02ee58
58 58
59 \defineUnit{nfa}{% 59 \defineUnit{nfa}{%
60 \begin{frame} 60 \begin{frame}
61 \frametitle{NFA} 61 \frametitle{NFA}
62 \begin{definition}[Nicht-Deterministischer endlicher Automat] 62 \begin{definition}[Nicht-Deterministischer endlicher Automat]
63 Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit 63 Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
64 \begin{itemize} 64 \begin{itemize}
65 \item $Q, \Sigma, q_0, F$ wie ein DFA 65 \item $Q, \Sigma, F$ wie ein DFA
66 \item Menge von \structure{Startzuständen} $S \subseteq F$
66 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$ 67 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
67 \end{itemize} 68 \end{itemize}
68 \end{definition} 69 \end{definition}
69 70
70 \vfill 71 \vfill
78 79
79 \defineUnit{enfa}{% 80 \defineUnit{enfa}{%
80 \begin{frame} 81 \begin{frame}
81 \frametitle{$\epsilon$-NFA} 82 \frametitle{$\epsilon$-NFA}
82 \begin{definition}[NFA mit $\epsilon$-Übergängen] 83 \begin{definition}[NFA mit $\epsilon$-Übergängen]
83 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit 84 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
84 \begin{itemize} 85 \begin{itemize}
85 \item $Q, \Sigma, q_0, F$ wie ein DFA 86 \item $Q, \Sigma, F$ wie ein DFA
87 \item Menge von \structure{Startzuständen} $S \subseteq F$
86 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$ 88 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$
87 \end{itemize} 89 \end{itemize}
88 \end{definition} 90 \end{definition}
89 91
90 \vfill 92 \vfill
326 \frametitle{NFA $\rightarrow$ DFA} 328 \frametitle{NFA $\rightarrow$ DFA}
327 \setbeamercovered{dynamic} 329 \setbeamercovered{dynamic}
328 330
329 \begin{block}{Potenzmengenkonstruktion} 331 \begin{block}{Potenzmengenkonstruktion}
330 Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt. 332 Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt.
331 Gegeben ein NFA $(Q, \Sigma, \delta, q_0, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}. 333 Gegeben ein NFA $(Q, \Sigma, \delta, S, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}.
332 334
333 \begin{itemize} 335 \begin{itemize}
334 \item Starte in $\left\{ q_0 \right\}$ 336 \item Starte in $\left\{ S \right\}$
335 \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte} 337 \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
336 \begin{align} 338 \begin{align}
337 \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\ 339 \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\
338 (S, a) &\mapsto \bigcup_{q \in S} \delta(q, a) 340 (M, a) &\mapsto \bigcup_{q \in M} \delta(q, a)
339 \end{align} 341 \end{align}
340 \item $S$ ist Endzustand wenn $F \cap S \neq \emptyset$ 342 \item $M$ ist Endzustand wenn $F \cap M \neq \emptyset$
341 \end{itemize} 343 \end{itemize}
342 \end{block} 344 \end{block}
343 345
344 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm] 346 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
345 \tikzstyle{every state}=[minimum width=1cm, pretty] 347 \tikzstyle{every state}=[minimum width=1cm, pretty]