Mercurial > 14ss.theoinf

comparison notes/tex/automata.tex @ 37:112bd0d1fa86 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix NFA definition - thanks Hendrik!
author Markus Kaiser <markus.kaiser@in.tum.de>
date Fri, 18 Jul 2014 21:54:34 +0200
parents f7bcd68a0c12
children
comparison
equal deleted inserted replaced
36:531fdbd3ed92 37:112bd0d1fa86
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, S, 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, F$ wie ein DFA 65 \item $Q, \Sigma, F$ wie ein DFA
66 \item Menge von \structure{Startzuständen} $S \subseteq F$ 66 \item Menge von \structure{Startzuständen} $S \subseteq Q$
67 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$ 67 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
68 \end{itemize} 68 \end{itemize}
69 \end{definition} 69 \end{definition}
70 70
71 \vfill 71 \vfill
82 \frametitle{$\epsilon$-NFA} 82 \frametitle{$\epsilon$-NFA}
83 \begin{definition}[NFA mit $\epsilon$-Übergängen] 83 \begin{definition}[NFA mit $\epsilon$-Übergängen]
84 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit 84 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
85 \begin{itemize} 85 \begin{itemize}
86 \item $Q, \Sigma, F$ wie ein DFA 86 \item $Q, \Sigma, F$ wie ein DFA
87 \item Menge von \structure{Startzuständen} $S \subseteq F$ 87 \item Menge von \structure{Startzuständen} $S \subseteq Q$
88 \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}$
89 \end{itemize} 89 \end{itemize}
90 \end{definition} 90 \end{definition}
91 91
92 \vfill 92 \vfill