Mercurial > 13ss.theoinf

comparison notes/tex/ue08_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 20168f32b94e
children 15351d87ce76
comparison
equal deleted inserted replaced
36:1098749b5645 37:27fedbbdab6d
16 16
17 \begin{definition}[Kellerautomat] 17 \begin{definition}[Kellerautomat]
18 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem 18 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
19 \begin{itemize} 19 \begin{itemize}
20 20
21 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ 21 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
22 \end{itemize} 22 \end{itemize}
23 \end{definition} 23 \end{definition}
24 24
25 \vfill 25 \vfill
26 26
53 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem 53 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
54 \begin{itemize} 54 \begin{itemize}
55 \item endlichen Menge von \alert{Zuständen} $Q$ 55 \item endlichen Menge von \alert{Zuständen} $Q$
56 \item endlichen \alert{Eingabealphabet} $\Sigma$ 56 \item endlichen \alert{Eingabealphabet} $\Sigma$
57 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ 57 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
58 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \mapsto Q \times \Gamma \times \left\{ L, R, N \right\}$ 58 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
59 \item \alert{Startzustand} $q_0 \in Q$ 59 \item \alert{Startzustand} $q_0 \in Q$
60 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ 60 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
61 \item Menge von \alert{Endzuständen} $F \subseteq Q$ 61 \item Menge von \alert{Endzuständen} $F \subseteq Q$
62 \end{itemize} 62 \end{itemize}
63 \end{definition} 63 \end{definition}
68 \setbeamercovered{dynamic} 68 \setbeamercovered{dynamic}
69 69
70 \begin{definition}[Turingmaschine] 70 \begin{definition}[Turingmaschine]
71 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem 71 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
72 \begin{itemize} 72 \begin{itemize}
73 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \mapsto Q \times \Gamma \times \left\{ L, R, N \right\}$ 73 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
74 \end{itemize} 74 \end{itemize}
75 \end{definition} 75 \end{definition}
76 76
77 \vfill 77 \vfill
78 78
167 167
168 \begin{definition}[Nichtdeterministische Turingmaschine] 168 \begin{definition}[Nichtdeterministische Turingmaschine]
169 Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem 169 Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
170 \begin{itemize} 170 \begin{itemize}
171 \item \ldots 171 \item \ldots
172 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \mapsto \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ 172 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$
173 \item \ldots 173 \item \ldots
174 \end{itemize} 174 \end{itemize}
175 \end{definition} 175 \end{definition}
176 176
177 \vfill 177 \vfill