Mercurial > 13ss.theoinf
changeset 37:27fedbbdab6d
change mapsto to to arrows
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 02 Jul 2013 14:16:16 +0200 |
| parents | 1098749b5645 |
| children | c498361ea492 |
| files | notes/tex/ue01_notes.tex notes/tex/ue02_notes.tex notes/tex/ue07_notes.tex notes/tex/ue08_notes.tex notes/tex/ue09_notes.tex notes/tex/ue10_notes.tex notes/ue01_notes.pdf notes/ue02_notes.pdf notes/ue03_notes.pdf notes/ue04_notes.pdf notes/ue05_notes.pdf notes/ue06_notes.pdf notes/ue07_notes.pdf notes/ue08_notes.pdf notes/ue09_notes.pdf notes/ue10_notes.pdf |
| diffstat | 16 files changed, 20 insertions(+), 20 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/ue01_notes.tex Tue Jul 02 00:59:43 2013 +0200 +++ b/notes/tex/ue01_notes.tex Tue Jul 02 14:16:16 2013 +0200 @@ -96,7 +96,7 @@ \begin{itemize} \item endlichen Menge von \alert{Zuständen} $Q$ \item endlichen \alert{Eingabealphabet} $\Sigma$ - \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto Q$ + \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$ \item \alert{Startzustand} $q_0 \in Q$ \item Menge von \alert{Endzuständen} $F \subseteq Q$ \end{itemize} @@ -127,7 +127,7 @@ Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit \begin{itemize} \item $Q, \Sigma, q_0, F$ wie ein DFA - \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto P(Q)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ \end{itemize} \end{definition} @@ -151,7 +151,7 @@ Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit \begin{itemize} \item $Q, \Sigma, q_0, F$ wie ein DFA - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \mapsto P(Q)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ \end{itemize} \end{definition} @@ -178,9 +178,9 @@ Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. \begin{description} - \item[DFA] $\delta : Q \times \Sigma \mapsto Q$ - \item[NFA] $\delta : Q \times \Sigma \mapsto \alert{P(Q)}$ - \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \mapsto \alert{P(Q)}$ + \item[DFA] $\delta : Q \times \Sigma \to Q$ + \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$ + \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$ \end{description} \end{block}
--- a/notes/tex/ue02_notes.tex Tue Jul 02 00:59:43 2013 +0200 +++ b/notes/tex/ue02_notes.tex Tue Jul 02 14:16:16 2013 +0200 @@ -211,7 +211,7 @@ Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}. \begin{itemize} - \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \mapsto P(Q)$ \\ + \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\ \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\] \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$ \end{itemize}
--- a/notes/tex/ue07_notes.tex Tue Jul 02 00:59:43 2013 +0200 +++ b/notes/tex/ue07_notes.tex Tue Jul 02 14:16:16 2013 +0200 @@ -64,7 +64,7 @@ \item endlichen Menge von \alert{Zuständen} $Q$ \item endlichen \alert{Eingabealphabet} $\Sigma$ \item endlichen \alert{Kelleralphabet} $\Gamma$ - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ \item \alert{Startzustand} $q_0 \in Q$ \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ \item Menge von \alert{Endzuständen} $F \subseteq Q$ @@ -88,7 +88,7 @@ \begin{definition}[Kellerautomat] Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem \begin{itemize} - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ \end{itemize} \end{definition} @@ -110,7 +110,7 @@ Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem \begin{itemize} - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ \end{itemize} \end{definition}
--- a/notes/tex/ue08_notes.tex Tue Jul 02 00:59:43 2013 +0200 +++ b/notes/tex/ue08_notes.tex Tue Jul 02 14:16:16 2013 +0200 @@ -18,7 +18,7 @@ Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem \begin{itemize} - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ \end{itemize} \end{definition} @@ -55,7 +55,7 @@ \item endlichen Menge von \alert{Zuständen} $Q$ \item endlichen \alert{Eingabealphabet} $\Sigma$ \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ - \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \mapsto Q \times \Gamma \times \left\{ L, R, N \right\}$ + \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ \item \alert{Startzustand} $q_0 \in Q$ \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ \item Menge von \alert{Endzuständen} $F \subseteq Q$ @@ -70,7 +70,7 @@ \begin{definition}[Turingmaschine] Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem \begin{itemize} - \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \mapsto Q \times \Gamma \times \left\{ L, R, N \right\}$ + \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ \end{itemize} \end{definition} @@ -169,7 +169,7 @@ Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem \begin{itemize} \item \ldots - \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \mapsto \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ \item \ldots \end{itemize} \end{definition}
--- a/notes/tex/ue09_notes.tex Tue Jul 02 00:59:43 2013 +0200 +++ b/notes/tex/ue09_notes.tex Tue Jul 02 14:16:16 2013 +0200 @@ -33,7 +33,7 @@ \setbeamercovered{dynamic} \begin{definition}[Intuitive Berechenbarkeit] - Eine Funktion $f : \N^k \mapsto \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ + Eine Funktion $f : \N^k \to \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ \begin{itemize} \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. @@ -102,7 +102,7 @@ \begin{itemize} \item Die konstante Funktion \alert{0} \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ - \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \mapsto \N, i \in [k]$ + \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$ \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] \end{itemize} \end{definition} @@ -121,7 +121,7 @@ \begin{itemize} \item Konstante: $0$ \item Nachfolger: $s(n) = n + 1$ - \item Projektion: $\pi_i^k : \N^k \mapsto \N$ + \item Projektion: $\pi_i^k : \N^k \to \N$ \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ \end{itemize} \end{block}
--- a/notes/tex/ue10_notes.tex Tue Jul 02 00:59:43 2013 +0200 +++ b/notes/tex/ue10_notes.tex Tue Jul 02 14:16:16 2013 +0200 @@ -78,7 +78,7 @@ \setbeamercovered{dynamic} \begin{definition}[$\mu$-Operator] - Sei $f: \N^{k+1} \mapsto \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \mapsto \N$: + Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$: \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\] \end{definition} @@ -128,7 +128,7 @@ \setbeamercovered{dynamic} \begin{definition}[Intuitive Berechenbarkeit] - Eine Funktion $f : \N^k \mapsto \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ + Eine Funktion $f : \N^k \to \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ \begin{itemize} \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. @@ -164,7 +164,7 @@ \setbeamercovered{dynamic} \begin{definition}[Reduzierbarkeit] - Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \mapsto \Gamma^*$ gibt mit + Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] Wir schreiben dann \alert{$A \leq B$}. \end{definition}