Mercurial > 13ss.theoinf

comparison notes/tex/ue01_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 1: Sprachen und Automaten} 4 \title{Übung 1: Sprachen und Automaten}
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{organisatorisches}
10 \titlepage 11 \showUnit{wasisttheo}
11 \end{frame} 12 \showUnit{alphabet}
12 13 \showUnit{dfa}
13 \begin{frame} 14 \showUnit{nfa}
14 \frametitle{Organisatorisches} 15 \showUnit{enfa}
15 16 \showUnit{automatenkonversionen}
16 \begin{itemize} 17 \showUnit{name}
17 \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org}
18 \item Web: \href{tutor.zfix.org}{tutor.zfix.org}
19 \vfill
20 \item Wann?
21 \begin{itemize}
22 \item Dienstag 10:15-11:45 00.08.038
23 \item Dienstag 12:05-13:35 00.08.038
24 \end{itemize}
25 \item Übungsablauf, Aufgabentypen
26 \item Hausaufgaben
27 \begin{itemize}
28 \item Abgabe am Montag 14h, \alert{allein}
29 \item Rückgabe in der \alert{richtigen} Übung
30 \item Notenbonus für 40\% der Punkte, 40\% in der zweiten Hälfte
31 \end{itemize}
32 \item Klausur
33 \begin{itemize}
34 \item Endterm: Mi 31.07. 11.30-14h
35 \item Wiederholung: Do 26.09. 11-13.30h
36 \end{itemize}
37 \end{itemize}
38 \end{frame}
39
40 \begin{frame}
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$
99 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
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
130 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$
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
154 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$
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}
181 \item[DFA] $\delta : Q \times \Sigma \to Q$
182 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$
183 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$
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}
219
220 \end{document} 18 \end{document}