Mercurial > 14ss.theoinf

comparison notes/tex/automatons.tex @ 11:de844d67518b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix powersets; wording
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sat, 26 Apr 2014 21:10:36 +0200
parents e1b3b7b99d28
children 11723d02ee58
comparison
equal deleted inserted replaced
10:e1b3b7b99d28 11:de844d67518b
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, q_0, F)$ mit
64 \begin{itemize} 64 \begin{itemize}
65 \item $Q, \Sigma, q_0, F$ wie ein DFA 65 \item $Q, \Sigma, q_0, F$ wie ein DFA
66 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ 66 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
67 \end{itemize} 67 \end{itemize}
68 \end{definition} 68 \end{definition}
69 69
70 \vfill 70 \vfill
71 71
81 \frametitle{$\epsilon$-NFA} 81 \frametitle{$\epsilon$-NFA}
82 \begin{definition}[NFA mit $\epsilon$-Übergängen] 82 \begin{definition}[NFA mit $\epsilon$-Übergängen]
83 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit 83 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
84 \begin{itemize} 84 \begin{itemize}
85 \item $Q, \Sigma, q_0, F$ wie ein DFA 85 \item $Q, \Sigma, q_0, F$ wie ein DFA
86 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ 86 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$
87 \end{itemize} 87 \end{itemize}
88 \end{definition} 88 \end{definition}
89 89
90 \vfill 90 \vfill
91 91
103 \begin{block}{Übergangsfunktionen} 103 \begin{block}{Übergangsfunktionen}
104 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. 104 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
105 105
106 \begin{description} 106 \begin{description}
107 \item[DFA] $\delta : Q \times \Sigma \to Q$ 107 \item[DFA] $\delta : Q \times \Sigma \to Q$
108 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$ 108 \item[NFA] $\delta : Q \times \Sigma \to \alert{\powerset{Q}}$
109 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$ 109 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{\powerset{Q}}$
110 \end{description} 110 \end{description}
111 \end{block} 111 \end{block}
112 112
113 \vfill 113 \vfill
114 114
332 332
333 \begin{itemize} 333 \begin{itemize}
334 \item Starte in $\left\{ q_0 \right\}$ 334 \item Starte in $\left\{ q_0 \right\}$
335 \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte} 335 \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
336 \begin{align} 336 \begin{align}
337 \overline{\delta}: \alert{\powerset{Q}} \times \Sigma &\to \powerset{Q} \\ 337 \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\
338 (S, a) &\mapsto \bigcup_{q \in S} \delta(q, a) 338 (S, a) &\mapsto \bigcup_{q \in S} \delta(q, a)
339 \end{align} 339 \end{align}
340 \item $S$ ist Endzustand wenn $F \cap S \neq \emptyset$ 340 \item $S$ ist Endzustand wenn $F \cap S \neq \emptyset$
341 \end{itemize} 341 \end{itemize}
342 \end{block} 342 \end{block}