Mercurial > 13ss.theoinf

comparison notes/tex/ue08_notes.tex @ 44:15351d87ce76

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
transition notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 22:06:26 +0200
parents 27fedbbdab6d
children
comparison
equal deleted inserted replaced
43:c14b92bfa07f 44:15351d87ce76
1 \input{preamble.tex} 1 \input{preamble.tex}
2 \input{frames.tex}
2 3
3 \title{Übung 8: Turingmaschinen} 4 \title{Übung 8: Turingmaschinen}
4 \subtitle{Theoretische Informatik Sommersemester 2013} 5 \subtitle{Theoretische Informatik Sommersemester 2013}
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
6 7
7 \begin{document} 8 \begin{document}
8 9 \showUnit{titel}
9 \begin{frame} 10 \showUnit{tmdefinition}
10 \titlepage 11 \showUnit{tmvisualisierung}
11 \end{frame} 12 \showUnit{ndtm}
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
21 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
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$
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$
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}
73 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
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
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
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} 13 \end{document}