Mercurial > 13ss.theoinf
annotate notes/tex/ue01_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 | 90ffda7e20c7 |
| children | 15351d87ce76 |
| rev | line source |
|---|---|
| 31 | 1 \input{preamble.tex} |
| 2 | 2 |
| 7 | 3 \title{Übung 1: Sprachen und Automaten} |
| 2 | 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} | |
|
3
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
14 \frametitle{Organisatorisches} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
15 |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
16 \begin{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
17 \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
18 \item Web: \href{tutor.zfix.org}{tutor.zfix.org} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
19 \vfill |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
20 \item Wann? |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
21 \begin{itemize} |
| 7 | 22 \item Dienstag 10:15-11:45 00.08.038 |
| 23 \item Dienstag 12:05-13:35 00.08.038 | |
|
3
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
24 \end{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
25 \item Übungsablauf, Aufgabentypen |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
26 \item Hausaufgaben |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
27 \begin{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
28 \item Abgabe am Montag 14h, \alert{allein} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
29 \item Rückgabe in der \alert{richtigen} Übung |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
30 \item Notenbonus für 40\% der Punkte, 40\% in der zweiten Hälfte |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
31 \end{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
32 \item Klausur |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
33 \begin{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
34 \item Endterm: Mi 31.07. 11.30-14h |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
35 \item Wiederholung: Do 26.09. 11-13.30h |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
36 \end{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
37 \end{itemize} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
38 \end{frame} |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
39 |
|
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
40 \begin{frame} |
| 2 | 41 \frametitle{Was ist Theoinf?} |
| 42 | |
| 43 Aus der VL | |
| 44 \vspace{1em} | |
| 45 | |
| 46 \begin{itemize} | |
| 47 \item Automatentheorie | |
| 48 \begin{itemize} | |
| 49 \item Rechner mit endlichem oder kellerartigem Speicher | |
| 50 \end{itemize} | |
| 51 \vspace{0.5em} | |
| 52 \item Grammatiken | |
| 53 \begin{itemize} | |
| 54 \item Syntax von Programmiersprachen | |
| 55 \end{itemize} | |
| 56 \vspace{0.5em} | |
| 57 \item Berechenbarkeitstheorie | |
| 58 \begin{itemize} | |
| 59 \item Untersuchung der Grenzen, was Rechner prinzipiell können | |
| 60 \end{itemize} | |
| 61 \vspace{0.5em} | |
| 62 \item Komplexitätstheorie | |
| 63 \begin{itemize} | |
| 64 \item Untersuchung der Grenzen, was Rechner mit begrenzten Ressourcen können | |
| 65 \end{itemize} | |
| 66 \end{itemize} | |
| 67 \end{frame} | |
| 68 | |
| 69 \begin{frame} | |
| 70 \frametitle{Grundlegendes} | |
| 71 | |
| 72 \begin{definition} | |
| 73 \begin{itemize} | |
| 74 \item Ein \alert{Alphabet} $\Sigma$ ist eine endliche Menge. | |
| 75 \item Ein \alert{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen. | |
| 76 \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \alert{formale Sprache} | |
| 77 \end{itemize} | |
| 78 \end{definition} | |
| 79 | |
| 80 \vfill | |
| 81 | |
| 82 \begin{definition}[Operationen auf Sprachen] | |
| 83 \begin{itemize} | |
| 84 \item $\alert{AB} = \left\{ uv \mid u \in A \wedge v \in B \right\}$ | |
| 85 \item $\alert{A^n} = \left\{w_1 \ldots w_n \mid w_1 \ldots w_n \in A \right\}$,\qquad $A^0 = \{\epsilon\}$ | |
| 86 \item $\alert{A^*} = \bigcup_{n \in \N_0} A^n$ | |
| 87 \end{itemize} | |
| 88 \end{definition} | |
| 89 \end{frame} | |
| 90 | |
| 91 \begin{frame} | |
| 92 \frametitle{DFA} | |
| 93 | |
| 94 \begin{definition}[Deterministischer endlicher Automat] | |
| 95 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem | |
| 96 \begin{itemize} | |
| 97 \item endlichen Menge von \alert{Zuständen} $Q$ | |
| 98 \item endlichen \alert{Eingabealphabet} $\Sigma$ | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
31
diff
changeset
|
99 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$ |
| 2 | 100 \item \alert{Startzustand} $q_0 \in Q$ |
| 101 \item Menge von \alert{Endzuständen} $F \subseteq Q$ | |
| 102 \end{itemize} | |
| 103 \end{definition} | |
| 104 | |
| 105 \vfill | |
| 106 \pause | |
| 107 | |
| 108 \begin{center} | |
| 109 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] | |
| 110 \node[state, initial] (q0) {$q_0$}; | |
| 111 \node[state, accepting] (q1) [right of = q0] {$q_1$}; | |
| 112 \node[state] (q2) [right of = q1] {$q_2$}; | |
| 113 | |
| 114 \draw[->] (q0) edge [loop above] node {0} (q0); | |
| 115 \draw[->] (q2) edge [loop above] node {1} (q2); | |
| 116 \draw[->] (q0) edge [bend left] node {1} (q1); | |
| 117 \draw[->] (q1) edge [bend left] node {1} (q0); | |
| 118 \draw[->] (q1) edge [bend left] node {0} (q2); | |
| 119 \draw[->] (q2) edge [bend left] node {0} (q1); | |
| 120 \end{tikzpicture} | |
| 121 \end{center} | |
| 122 \end{frame} | |
| 123 | |
| 124 \begin{frame} | |
| 125 \frametitle{NFA} | |
| 126 \begin{definition}[Nicht-Deterministischer endlicher Automat] | |
| 127 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit | |
| 128 \begin{itemize} | |
| 129 \item $Q, \Sigma, q_0, F$ wie ein DFA | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
31
diff
changeset
|
130 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ |
| 2 | 131 \end{itemize} |
| 132 \end{definition} | |
| 133 | |
| 134 \vfill | |
| 135 \pause | |
| 136 | |
| 137 \begin{center} | |
| 138 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] | |
| 139 \node[state, initial] (q0) {$q_0$}; | |
| 140 \node[state, accepting] (q1) [right of = q0] {$q_1$}; | |
| 141 | |
| 142 \draw[->] (q0) edge [loop above] node {0,1} (q0); | |
| 143 \draw[->] (q0) edge node {1} (q1); | |
| 144 \end{tikzpicture} | |
| 145 \end{center} | |
| 146 \end{frame} | |
| 147 | |
| 148 \begin{frame} | |
| 149 \frametitle{$\epsilon$-NFA} | |
| 150 \begin{definition}[NFA mit $\epsilon$-Übergängen] | |
| 151 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit | |
| 152 \begin{itemize} | |
| 153 \item $Q, \Sigma, q_0, F$ wie ein DFA | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
31
diff
changeset
|
154 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ |
| 2 | 155 \end{itemize} |
| 156 \end{definition} | |
| 157 | |
| 158 \vfill | |
| 159 \pause | |
| 160 | |
| 161 \begin{center} | |
| 162 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=] | |
| 163 \node[state] (q1) {$q_1$}; | |
| 164 \node[state, initial] (q0) [left of = q1] {$q_0$}; | |
| 165 \node[state, accepting] (q2) [right of = q1] {$q_2$}; | |
| 166 | |
| 167 \draw[->] (q0) edge [red] node {$\epsilon$} (q1); | |
| 168 \draw[->] (q1) edge [loop above] node {0,1} (q1); | |
| 169 \draw[->] (q1) edge node {1} (q2); | |
| 170 \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2); | |
| 171 \end{tikzpicture} | |
| 172 \end{center} | |
| 173 \end{frame} | |
| 174 | |
| 175 \begin{frame} | |
| 176 \frametitle{Automaten} | |
| 177 \begin{block}{Übergangsfunktionen} | |
| 178 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. | |
| 179 | |
| 180 \begin{description} | |
|
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
31
diff
changeset
|
181 \item[DFA] $\delta : Q \times \Sigma \to Q$ |
|
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
31
diff
changeset
|
182 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$ |
|
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
31
diff
changeset
|
183 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$ |
| 2 | 184 \end{description} |
| 185 \end{block} | |
| 186 | |
| 187 \vfill | |
| 188 | |
| 189 \begin{theorem} | |
| 190 \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln. | |
| 191 \end{theorem} | |
| 192 \end{frame} | |
| 193 | |
| 194 \begin{frame} | |
| 195 \frametitle{Tutoraufgabe 3} | |
| 196 | |
| 197 \begin{center} | |
| 198 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] | |
| 199 \node[state, initial] (q0) {$q_0$}; | |
| 200 \node[state, accepting] (q1) [above right of = q0] {$q_1$}; | |
| 201 \node[state] (q2) [right of = q1] {$q_2$}; | |
| 202 \node[state] (q3) [below right of = q0] {$q_3$}; | |
| 203 \node[state] (q4) [right of = q3] {$q_4$}; | |
| 204 | |
| 205 \draw[->] (q0) edge node {0} (q1); | |
| 206 \draw[->] (q0) edge node {1} (q3); | |
| 207 | |
| 208 \draw[->] (q1) edge [loop above] node {0} (q1); | |
| 209 \draw[->] (q2) edge [loop right] node {1} (q2); | |
| 210 \draw[->] (q4) edge [loop right] node {0} (q4); | |
| 211 | |
| 212 \draw[->] (q1) edge [bend left] node {1} (q2); | |
| 213 \draw[->] (q2) edge [bend left] node {0} (q1); | |
| 214 \draw[->] (q3) edge [bend left] node {0,1} (q4); | |
| 215 \draw[->] (q4) edge [bend left] node {1} (q3); | |
| 216 \end{tikzpicture} | |
| 217 \end{center} | |
| 218 \end{frame} | |
|
3
73037b3dde60
add organisatorical slide
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
2
diff
changeset
|
219 |
| 2 | 220 \end{document} |