Mercurial > 13ss.theoinf

comparison notes/tex/ue01_notes.tex @ 37:27fedbbdab6d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change mapsto to to arrows
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 02 Jul 2013 14:16:16 +0200
parents 90ffda7e20c7
children 15351d87ce76
comparison
equal deleted inserted replaced
36:1098749b5645 37:27fedbbdab6d
94 \begin{definition}[Deterministischer endlicher Automat] 94 \begin{definition}[Deterministischer endlicher Automat]
95 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem 95 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
96 \begin{itemize} 96 \begin{itemize}
97 \item endlichen Menge von \alert{Zuständen} $Q$ 97 \item endlichen Menge von \alert{Zuständen} $Q$
98 \item endlichen \alert{Eingabealphabet} $\Sigma$ 98 \item endlichen \alert{Eingabealphabet} $\Sigma$
99 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto Q$ 99 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
100 \item \alert{Startzustand} $q_0 \in Q$ 100 \item \alert{Startzustand} $q_0 \in Q$
101 \item Menge von \alert{Endzuständen} $F \subseteq Q$ 101 \item Menge von \alert{Endzuständen} $F \subseteq Q$
102 \end{itemize} 102 \end{itemize}
103 \end{definition} 103 \end{definition}
104 104
125 \frametitle{NFA} 125 \frametitle{NFA}
126 \begin{definition}[Nicht-Deterministischer endlicher Automat] 126 \begin{definition}[Nicht-Deterministischer endlicher Automat]
127 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit 127 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
128 \begin{itemize} 128 \begin{itemize}
129 \item $Q, \Sigma, q_0, F$ wie ein DFA 129 \item $Q, \Sigma, q_0, F$ wie ein DFA
130 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto P(Q)$ 130 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$
131 \end{itemize} 131 \end{itemize}
132 \end{definition} 132 \end{definition}
133 133
134 \vfill 134 \vfill
135 \pause 135 \pause
149 \frametitle{$\epsilon$-NFA} 149 \frametitle{$\epsilon$-NFA}
150 \begin{definition}[NFA mit $\epsilon$-Übergängen] 150 \begin{definition}[NFA mit $\epsilon$-Übergängen]
151 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit 151 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
152 \begin{itemize} 152 \begin{itemize}
153 \item $Q, \Sigma, q_0, F$ wie ein DFA 153 \item $Q, \Sigma, q_0, F$ wie ein DFA
154 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \mapsto P(Q)$ 154 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$
155 \end{itemize} 155 \end{itemize}
156 \end{definition} 156 \end{definition}
157 157
158 \vfill 158 \vfill
159 \pause 159 \pause
176 \frametitle{Automaten} 176 \frametitle{Automaten}
177 \begin{block}{Übergangsfunktionen} 177 \begin{block}{Übergangsfunktionen}
178 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. 178 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
179 179
180 \begin{description} 180 \begin{description}
181 \item[DFA] $\delta : Q \times \Sigma \mapsto Q$ 181 \item[DFA] $\delta : Q \times \Sigma \to Q$
182 \item[NFA] $\delta : Q \times \Sigma \mapsto \alert{P(Q)}$ 182 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$
183 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \mapsto \alert{P(Q)}$ 183 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$
184 \end{description} 184 \end{description}
185 \end{block} 185 \end{block}
186 186
187 \vfill 187 \vfill
188 188