Mercurial > 13ss.theoinf
annotate notes/tex/ue08_notes.tex @ 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 | 20168f32b94e |
| children | 15351d87ce76 |
| rev | line source |
|---|---|
| 32 | 1 \input{preamble.tex} |
| 2 | |
| 3 \title{Übung 8: Turingmaschinen} | |
| 4 \subtitle{Theoretische Informatik Sommersemester 2013} | |
| 5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} | |
| 6 | |
| 7 \begin{document} | |
| 8 | |
| 9 \begin{frame} | |
| 10 \titlepage | |
| 11 \end{frame} | |
| 12 | |
| 13 \begin{frame} | |
| 14 \frametitle{Kellerautomat} | |
| 15 \setbeamercovered{dynamic} | |
| 16 | |
| 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 | |
| 19 \begin{itemize} | |
| 20 | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
32
diff
changeset
|
21 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$ |
| 32 | 22 \end{itemize} |
| 23 \end{definition} | |
| 24 | |
| 25 \vfill | |
| 26 | |
| 27 \begin{example}[] | |
| 28 PDA akzeptierend \alert{mit leerem Keller} zu $L = \left\{ a^nb^n \mid n \in \N \right\}$. | |
| 29 | |
| 30 \centering | |
| 31 \begin{tikzpicture}[automaton] | |
| 32 | |
| 33 \node[state, initial] (q0) {$q_0$}; | |
| 34 \node[state] (q1) [right of = q0] {$q_1$}; | |
| 35 | |
| 36 \draw[->] (q0) edge [bend left] node {$\epsilon, A/A$} (q1); | |
| 37 \draw[->] (q0) edge [bend right] node [below] {$\epsilon, Z_0/Z_0$} (q1); | |
| 38 | |
| 39 \draw[->] (q0) edge [loop above] node {$a, Z_0/AZ_0$} (q0); | |
| 40 \draw[->] (q0) edge [loop below] node {$a, A/AA$} (q0); | |
| 41 | |
| 42 \draw[->] (q1) edge [loop above] node {$b, A/\epsilon$} (q1); | |
| 43 \draw[->] (q1) edge [loop below] node {$\epsilon, Z_0/\epsilon$} (q1); | |
| 44 \end{tikzpicture} | |
| 45 \end{example} | |
| 46 \end{frame} | |
| 47 | |
| 48 \begin{frame} | |
| 49 \frametitle{Turingmaschinen} | |
| 50 \setbeamercovered{dynamic} | |
| 51 | |
| 52 \begin{definition}[Turingmaschine] | |
| 53 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem | |
| 54 \begin{itemize} | |
| 55 \item endlichen Menge von \alert{Zuständen} $Q$ | |
| 56 \item endlichen \alert{Eingabealphabet} $\Sigma$ | |
| 57 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
32
diff
changeset
|
58 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ |
| 32 | 59 \item \alert{Startzustand} $q_0 \in Q$ |
| 60 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ | |
| 61 \item Menge von \alert{Endzuständen} $F \subseteq Q$ | |
| 62 \end{itemize} | |
| 63 \end{definition} | |
| 64 \end{frame} | |
| 65 | |
| 66 \begin{frame} | |
| 67 \frametitle{Turingmaschinen} | |
| 68 \setbeamercovered{dynamic} | |
| 69 | |
| 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 | |
| 72 \begin{itemize} | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
32
diff
changeset
|
73 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ |
| 32 | 74 \end{itemize} |
| 75 \end{definition} | |
| 76 | |
| 77 \vfill | |
| 78 | |
| 79 \begin{center} | |
| 80 \begin{tikzpicture} | |
| 81 % Tape | |
| 82 \begin{scope}[start chain, node distance=0] | |
| 83 \node[on chain] {\ldots}; | |
| 84 \node[tape] {$\square$}; | |
| 85 \node[tape] (l) {$\square$}; | |
| 86 \node[tape] {$0$}; | |
| 87 \node[tape] {$1$}; | |
| 88 \node<1>[tape, active] (a){$0$}; | |
| 89 \node<2>[tape] (a){$1$}; | |
| 90 \node<1>[tape] (b){$0$}; | |
| 91 \node<2>[tape, active] (b){$0$}; | |
| 92 \node[tape] {$\square$}; | |
| 93 \node[on chain] {\ldots}; | |
| 94 \end{scope} | |
| 95 | |
| 96 % Head | |
| 97 \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$}; | |
| 98 \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$}; | |
| 99 | |
| 100 % Machine | |
| 101 \node[machine, below=1.5cm of l] (machine) {Programm}; | |
| 102 \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south); | |
| 103 | |
| 104 % Example-Transition | |
| 105 \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$}; | |
| 106 \end{tikzpicture} | |
| 107 \end{center} | |
| 108 \end{frame} | |
| 109 | |
| 110 \begin{frame} | |
| 111 \frametitle{Turingmaschinen} | |
| 112 \setbeamercovered{dynamic} | |
| 113 | |
| 114 \begin{definition}[Konfiguration] | |
| 115 Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\ | |
| 116 Dies modelliert eine TM mit: | |
| 117 \begin{itemize} | |
| 118 \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$ | |
| 119 \item \alert{Zustand} $q$ | |
| 120 \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$ | |
| 121 \end{itemize} | |
| 122 Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$. | |
| 123 \end{definition} | |
| 124 | |
| 125 \vfill | |
| 126 | |
| 127 \only<1> { | |
| 128 \begin{center} | |
| 129 \begin{tikzpicture} | |
| 130 % Tape | |
| 131 \begin{scope}[start chain, node distance=0] | |
| 132 \node[on chain] {\ldots}; | |
| 133 \node[tape] {$\square$}; | |
| 134 \node[tape] (l) {$\square$}; | |
| 135 \node[tape] {$0$}; | |
| 136 \node[tape] {$1$}; | |
| 137 \node[tape] (a){$1$}; | |
| 138 \node[tape, active] (b){$0$}; | |
| 139 \node[tape] {$\square$}; | |
| 140 \node[on chain] {\ldots}; | |
| 141 \end{scope} | |
| 142 | |
| 143 % Head | |
| 144 \node [head,yshift=-4mm] at (b.south) (head) {$q_1$}; | |
| 145 | |
| 146 % Machine | |
| 147 \node[below=1.5cm of l] (machine) {}; | |
| 148 \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south); | |
| 149 | |
| 150 % Example-Transition | |
| 151 \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$}; | |
| 152 \end{tikzpicture} | |
| 153 \end{center} | |
| 154 } | |
| 155 | |
| 156 \only<2> { | |
| 157 \begin{definition}[Akzeptanz] | |
| 158 Eine TM $M$ \alert{akzeptiert} die Sprache | |
| 159 \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \] | |
| 160 \end{definition} | |
| 161 } | |
| 162 \end{frame} | |
| 163 | |
| 164 \begin{frame} | |
| 165 \frametitle{Nichtdeterministische TM} | |
| 166 \setbeamercovered{dynamic} | |
| 167 | |
| 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 | |
| 170 \begin{itemize} | |
| 171 \item \ldots | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
32
diff
changeset
|
172 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ |
| 32 | 173 \item \ldots |
| 174 \end{itemize} | |
| 175 \end{definition} | |
| 176 | |
| 177 \vfill | |
| 178 | |
| 179 \begin{theorem} | |
| 180 Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}. | |
| 181 \end{theorem} | |
| 182 \end{frame} | |
| 183 | |
| 184 \end{document} |