Mercurial > 14ss.theoinf

comparison notes/tex/automata.tex @ 15:60757c0ba1f0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rename automata file; add complete notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Fri, 09 May 2014 11:28:33 +0200
parents notes/tex/automatons.tex@d5b561a49683
children a08f6e33cfb0
comparison
equal deleted inserted replaced
14:d5b561a49683 15:60757c0ba1f0
1 \defineUnit{alphabet}{%
2 \begin{frame}
3 \frametitle{Alphabete}
4
5 \begin{definition}
6 \begin{itemize}
7 \item Ein \structure{Alphabet} $\Sigma$ ist eine endliche Menge.
8 \item Ein \structure{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen.
9 \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \structure{formale Sprache}
10 \end{itemize}
11 \end{definition}
12
13 \vfill
14
15 \begin{definition}[Operationen auf Sprachen]
16 \begin{itemize}
17 \item $\structure{AB} \defeq \left\{ uv \mid u \in A \wedge v \in B \right\}$
18 \item $\structure{A^{n+1}} \defeq A^nA $,\qquad\qquad $\structure{A^0} \defeq \{\epsilon\}$
19 \item $\structure{A^*} \defeq \bigcup_{n \in \N_0} A^n$
20 \end{itemize}
21 \end{definition}
22 \end{frame}
23 }
24
25 \defineUnit{dfa}{%
26 \begin{frame}
27 \frametitle{DFA}
28
29 \begin{definition}[Deterministischer endlicher Automat]
30 Ein \structure{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
31 \begin{itemize}
32 \item endlichen Menge von \structure{Zuständen} $Q$
33 \item endlichen \structure{Eingabealphabet} $\Sigma$
34 \item totalen \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
35 \item \structure{Startzustand} $q_0 \in Q$
36 \item Menge von \structure{Endzuständen} $F \subseteq Q$
37 \end{itemize}
38 \end{definition}
39
40 \vfill
41
42 \begin{center}
43 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
44 \node[state, initial] (q0) {$q_0$};
45 \node[state, accepting] (q1) [right of = q0] {$q_1$};
46 \node[state] (q2) [right of = q1] {$q_2$};
47
48 \draw[->] (q0) edge [loop above] node {0} (q0);
49 \draw[->] (q2) edge [loop above] node {1} (q2);
50 \draw[->] (q0) edge [bend left] node {1} (q1);
51 \draw[->] (q1) edge [bend left] node {1} (q0);
52 \draw[->] (q1) edge [bend left] node {0} (q2);
53 \draw[->] (q2) edge [bend left] node {0} (q1);
54 \end{tikzpicture}
55 \end{center}
56 \end{frame}
57 }
58
59 \defineUnit{nfa}{%
60 \begin{frame}
61 \frametitle{NFA}
62 \begin{definition}[Nicht-Deterministischer endlicher Automat]
63 Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
64 \begin{itemize}
65 \item $Q, \Sigma, F$ wie ein DFA
66 \item Menge von \structure{Startzuständen} $S \subseteq F$
67 \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$
68 \end{itemize}
69 \end{definition}
70
71 \vfill
72
73 \begin{center}
74 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
75 \node[state, initial] (q0) {$q_0$};
76 \node[state, accepting] (q1) [right of = q0] {$q_1$};
77 \draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame}
78 }
79
80 \defineUnit{enfa}{%
81 \begin{frame}
82 \frametitle{$\epsilon$-NFA}
83 \begin{definition}[NFA mit $\epsilon$-Übergängen]
84 Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, S, F)$ mit
85 \begin{itemize}
86 \item $Q, \Sigma, F$ wie ein DFA
87 \item Menge von \structure{Startzuständen} $S \subseteq F$
88 \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$
89 \end{itemize}
90 \end{definition}
91
92 \vfill
93
94 \begin{center}
95 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]
96 \node[state] (q1) {$q_1$};
97 \node[state, initial] (q0) [left of = q1] {$q_0$};
98 \node[state, accepting] (q2) [right of = q1] {$q_2$};
99 \draw[->] (q0) edge [red] node {$\epsilon$} (q1); \draw[->] (q1) edge [loop above] node {0,1} (q1); \draw[->] (q1) edge node {1} (q2); \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2); \end{tikzpicture} \end{center} \end{frame}
100 }
101
102 \defineUnit{endlicheautomaten}{%
103 \begin{frame}
104 \frametitle{Endliche Automaten}
105 \begin{block}{Übergangsfunktionen}
106 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
107
108 \begin{description}
109 \item[DFA] $\delta : Q \times \Sigma \to Q$
110 \item[NFA] $\delta : Q \times \Sigma \to \alert{\powerset{Q}}$
111 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{\powerset{Q}}$
112 \end{description}
113 \end{block}
114
115 \vfill
116
117 \begin{theorem}
118 \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln.
119 \end{theorem}
120 \end{frame}
121 }
122
123 \defineUnit{regex}{%
124 \begin{frame}
125 \frametitle{Reguläre Ausdrücke}
126 \setbeamercovered{dynamic}
127
128 \begin{definition}[Regulärer Ausdruck]
129 \structure{Reguläre Ausdrücke} sind induktiv definiert
130 \begin{itemize}
131 \item \structure{$\emptyset$} ist ein regulärer Ausdruck
132 \item \structure{$\epsilon$} ist ein regulärer Ausdruck
133 \item Für alle $a \in \Sigma$ ist \structure{$a$} ein regulärer Ausdruck
134 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
135 \begin{description}[Konkatenation]
136 \item[Konkatenation] \structure{$\alpha\beta$}
137 \item[Veroderung] \structure{$\alpha \mid \beta$}
138 \item[Wiederholung] \structure{$\alpha^*$}
139 \end{description}
140 \end{itemize}
141 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
142 \end{definition}
143
144 \begin{example}
145 \begin{itemize}
146 \item $\alpha = (0|1)^*00$
147 \item Worte bestehen aus einer beliebigen Folge von Einsen und Nullen gefolgt von zwei Nullen.
148 \item $L(\alpha) \supseteq \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
149 \end{itemize}
150 \end{example}
151 \end{frame}
152 }
153
154 \defineUnit{automatenkonversionen}{%
155 \begin{frame}[c]
156 \frametitle{Konversionen}
157 \setbeamercovered{dynamic}
158
159 \begin{center}
160 \begin{tikzpicture}[node distance=2cm]
161 \node (nfa) {NFA};
162 \node (dfa) [left of=nfa] {DFA};
163 \node (enfa) [right of=nfa] {$\epsilon$-NFA};
164 \node (re) [below of=nfa] {RE};
165
166 \draw [every edge, tumred] (nfa) -- (dfa);
167 \draw [every edge, tumred] (enfa) -- (nfa);
168 \draw [every edge] (dfa) -- (re);
169 \draw [every edge] (nfa) -- (re);
170 \draw [every edge, tumred] (re) -- (enfa);
171 \end{tikzpicture}
172 \end{center}
173 \end{frame}
174 }
175
176 \defineUnit{rezuenfa}{%
177 \begin{frame}
178 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
179 \setbeamercovered{dynamic}
180
181 \begin{block}{Thompson-Konstruktion}
182 Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert.
183 \end{block}
184
185 \begin{tabu} to \linewidth {XXX}
186 \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\
187 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
188 \node[state, initial] () {};
189 \end{tikzpicture} &
190
191 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
192 \node[state, initial, accepting] () {};
193 \end{tikzpicture} &
194
195 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
196 \node[state, initial] (i) {};
197 \node[state, accepting] (j) [right of=i] {};
198
199 \draw[->] (i) edge node {$a$} (j);
200 \end{tikzpicture} \\
201 \vspace{2em}
202 \alert{$\gamma = \alpha\beta$} \\
203 \multicolumn3{c}{
204 \begin{tikzpicture}[automaton, small]
205 \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1);
206 \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$};
207
208 \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1);
209 \node[tumgreen] () at (4.75, -1.2) {$N_\beta$};
210
211 \node[state, initial] (i) at (0, 0) {};
212 \node[state] (j) at (1.5, 0.5) {};
213 \node[state] (k) at (1.5, -0.5) {};
214 \node[state] (l) at (4, 0) {};
215 \node[state, accepting] (m) at (5.5, 0) {};
216
217 \draw[->] (j) edge node {$\epsilon$} (l);
218 \draw[->] (k) edge node {$\epsilon$} (l);
219 \end{tikzpicture}
220 }\\
221 \end{tabu}
222 \end{frame}
223
224 \begin{frame}
225 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
226 \setbeamercovered{dynamic}
227
228 \begin{tabu} to \linewidth {X}
229 \alert{$\gamma = \alpha \mid \beta$} \\
230 \centering
231 \begin{tikzpicture}[automaton, small]
232 \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5);
233 \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$};
234
235 \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5);
236 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$};
237
238 \node[state, initial] (i) at (0, 0) {};
239
240 \node[state] (j) at (2.5, 1) {};
241 \node[state] (k) at (4, 1) {};
242 \node[state] (l) at (2.5, -1) {};
243 \node[state] (m) at (4, -1) {};
244
245 \node[state, accepting] (n) at (6.5, 0) {};
246
247 \draw[->] (i) edge node {$\epsilon$} (j);
248 \draw[->] (i) edge node {$\epsilon$} (l);
249 \draw[->] (k) edge node {$\epsilon$} (n);
250 \draw[->] (m) edge node {$\epsilon$} (n);
251 \end{tikzpicture} \\
252 \vfill
253
254 \alert{$\gamma = \alpha^*$} \\
255 \centering
256 \begin{tikzpicture}[automaton, small, bend angle=70]
257 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);
258 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};
259
260 \node[state, initial] (i) at (0, 0) {};
261
262 \node[state] (j) at (2.5, 0) {};
263 \node[state] (k) at (4, 0.5) {};
264 \node[state] (m) at (4, -0.5) {};
265
266 \node[state, accepting] (n) at (6.5, 0) {};
267
268 \draw[->] (i) edge node {$\epsilon$} (j);
269 \draw[->] (i) edge[bend right=90] node {$\epsilon$} (n);
270
271 \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
272 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
273 \draw[->] (k) edge node {$\epsilon$} (n);
274 \draw[->] (m) edge node {$\epsilon$} (n);
275 \end{tikzpicture}
276 \end{tabu}
277 \end{frame}
278 }
279
280 \defineUnit{enfazunfa}{%
281 \begin{frame}
282 \frametitle{$\epsilon$-NFA $\rightarrow$ NFA}
283 \setbeamercovered{dynamic}
284
285 \begin{block}{Idee}
286 Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen.
287 \begin{enumerate}
288 \item<1-> Entferne \alert{unnötige Knoten}.
289 \item<1,3-> Für jeden \alert{Pfad} der Form $\epsilon\ldots\epsilon \alert{a} \epsilon\ldots\epsilon$ verbinde Anfangs- und Endknoten mit einer \alert{$a$}-Kante.
290 \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten.
291 \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand.
292 \end{enumerate}
293 \end{block}
294
295 \vfill
296
297 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm]
298 \useasboundingbox (-1.4,2) rectangle (9, -2);
299
300 \node<-4>[state, initial] (q0) {$q_0$};
301 \node[state] (q2) [right = 3.2cm of q0] {$q_2$};
302 \node[state] (q3) [right of = q2] {$q_3$};
303 \node[state, accepting] (q4) [right of = q3] {$q_4$};
304
305 \draw[->] (q2) edge node {$0$} (q3);
306 \draw[->] (q3) edge node {$1$} (q4);
307
308 \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
309 \draw[->] (q4) edge [bend right] node [above] {$1$} (q3);
310 \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
311
312 \node<1>[state] (q1) [right of = q0] {$q_1$};
313 \draw<1>[->] (q0) edge node {$\epsilon$} (q1);
314 \draw<1>[->] (q1) edge node {$1$} (q2);
315
316 \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$};
317 \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1);
318 \draw<2>[->, tumred] (q1) edge node {$0$} (q2);
319 \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2);
320
321 \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
322 \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3);
323 \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
324 \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2);
325
326 \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2);
327 \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3);
328 \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3);
329 \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2);
330
331 \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$};
332
333 \node<6->[state, initial, accepting] (q0) {$q_0$};
334 \end{tikzpicture}
335 \end{frame}
336 }
337
338 \defineUnit{nfazudfa}{%
339 \begin{frame}
340 \frametitle{NFA $\rightarrow$ DFA}
341 \setbeamercovered{dynamic}
342
343 \begin{block}{Potenzmengenkonstruktion}
344 Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt.
345 Gegeben ein NFA $(Q, \Sigma, \delta, S, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}.
346
347 \begin{itemize}
348 \item Starte in $\left\{ S \right\}$
349 \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte}
350 \begin{align}
351 \overline{\delta}: \powerset{Q} \times \Sigma &\to \powerset{Q} \\
352 (M, a) &\mapsto \bigcup_{q \in M} \delta(q, a)
353 \end{align}
354 \item $M$ ist Endzustand wenn $F \cap M \neq \emptyset$
355 \end{itemize}
356 \end{block}
357
358 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
359 \tikzstyle{every state}=[minimum width=1cm, pretty]
360 \useasboundingbox (-1.4,2) rectangle (9, -2);
361
362 \node[state, initial] (q0) {$q_0$};
363 \node[state, accepting] (q1) [right of = q0] {$q_1$};
364
365 \draw[->] (q0) edge [loop above] node {$0,1$} (q0);
366 \draw[->] (q0) edge node {$1$} (q1);
367
368 \node<2->(sep) [right of = q1] {$\rightarrow$};
369
370 \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$};
371
372 \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$};
373 \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0);
374 \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01);
375
376 \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01);
377 \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0);
378
379 \end{tikzpicture}
380 \end{frame}
381 }
382
383 \defineUnit{produktautomat}{%
384 \begin{frame}
385 \frametitle{Produktautomat}
386 \setbeamercovered{dynamic}
387
388 \begin{theorem}
389 Sind $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ und $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$ DFAs, dann ist der \alert{Produkt-Automat}
390
391 \begin{align*}
392 M &:= (\alert{Q_1 \times Q_2}, \Sigma, \delta, (s_1, s_2), F_1 \times F_2) \\
393 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right)
394 \end{align*}
395
396 ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert.
397 \end{theorem}
398 \end{frame}
399 }
400
401 \defineUnit{regexrechnen}{%
402 \begin{frame}
403 \frametitle{Nochmal Reguläre Ausdrücke}
404 \setbeamercovered{dynamic}
405
406 \begin{theorem}
407 Die regulären Ausdrücke $\mathfrak{R}$ über einem Alphabet $\Sigma$ bilden mit Konkatenation $\circ$ und Veroderung $\mid$ einen \alert{Halbring} $\langle \mathfrak{R}, \mid, \circ, \emptyset, \epsilon \rangle$.
408
409 \begin{itemize}
410 \item \alert{Assoziative} Operationen
411 \item Veroderung \alert{kommutativ}
412 \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$
413 \item $\emptyset$ \alert{neutral} bezüglich Oder
414 \item $\epsilon$ \alert{neutral} bezüglich Konkatenation
415 \end{itemize}
416 \end{theorem}
417
418 \begin{example}
419 \[
420 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi
421 \]
422 \end{example}
423 \end{frame}
424 }
425
426 \defineUnit{arden}{%
427 \begin{frame}
428 \frametitle{Ardens Lemma}
429 \setbeamercovered{dynamic}
430
431 \begin{theorem}[Ardens Lemma]
432 Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt
433 \[
434 X = AX \cup B \Longrightarrow X = A^* B
435 \]
436 Speziell gilt für reguläre Ausdrücke
437 \[
438 X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta
439 \]
440 \end{theorem}
441
442 \begin{example}
443 \[
444 \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi
445 \]
446 \end{example}
447 \end{frame}
448 }
449
450 \defineUnit{nfazure}{%
451 \begin{frame}
452 \frametitle{NFA $\rightarrow$ RE}
453 \setbeamercovered{dynamic}
454
455 \begin{block}{Idee}
456 Erzeuge ein Gleichungssystem aus allen Zuständen.
457 \begin{enumerate}
458 \item<1,2-> Ausdruck für jeden Zustand
459 \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma
460 \end{enumerate}
461 \end{block}
462 \begin{columns}<2->
463 \begin{column}[b]{.65\textwidth}
464 \begin{align*}
465 X_0 &\equiv 1X_0 \mid 0X_1 \\
466 &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\
467 &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\
468 &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\
469 \\
470 X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\
471 &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\
472 &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}}
473 \end{align*}
474 \end{column}
475 \begin{column}[t]{.35\textwidth}
476 \begin{tikzpicture}[automaton]
477 \node[state, initial] (q0) {$q_0$};
478 \node[state, accepting] (q1) [below of=q0] {$q_1$};
479
480 \draw[->] (q0) edge [bend right] node [left] {$0$} (q1);
481 \draw[->] (q1) edge [bend right] node [right] {$1$} (q0);
482 \draw[->] (q0) edge [loop right] node {$1$} (q0);
483 \draw[->] (q1) edge [loop right] node {$0$} (q1);
484 \end{tikzpicture}
485 \end{column}
486 \end{columns}
487 \end{frame}
488 }
489
490 \defineUnit{rpl}{%
491 \begin{frame}
492 \frametitle{Pumping Lemma}
493 \setbeamercovered{dynamic}
494
495 \begin{theorem}[Pumping Lemma für reguläre Sprachen]
496 Sei $R \subseteq \Sigma^*$ regulär. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in R$ mit $|z| \geq n$ so in $z = uvw$ zerlegen lässt, dass
497 \begin{itemize}
498 \item $v \neq \epsilon$
499 \item $|uv| \alert{\leq n}$
500 \item $\forall i \alert{\geq 0}. uv^iw \in R$
501 \end{itemize}
502 \end{theorem}
503
504 \vfill
505
506 \begin{center}
507 \begin{tikzpicture}[automaton]
508 \node[state, initial] (q0) {};
509 \node[state, fill=tumred!20] (q1) [right of=q0] {};
510 \node[state, accepting] (q2) [right of=q1] {};
511
512 \draw[->, densely dashed] (q0) edge node {$u$} (q1);
513 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1);
514 \draw[->, densely dashed] (q1) edge node {$w$} (q2);
515 \end{tikzpicture}
516 \end{center}
517 \end{frame}
518 }
519
520 \defineUnit{rplanwenden}{%
521 \begin{frame}
522 \frametitle{Nichtregularität beweisen}
523 \setbeamercovered{dynamic}
524
525 \begin{block}{Idee}
526 Gegenbeispiel fürs Pumpinglemma suchen.
527 \[
528 \alert{\forall} n \in \N_0 \alert{\exists} z \in L. |z| \geq n \ \alert{\forall} u,v,w. \ z = uvw \ \text{\alert{nicht} pumpbar}
529 \]
530 \end{block}
531
532 \vfill
533
534 \begin{example}<2->
535 Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär?
536 \begin{enumerate}
537 \item \alert{Sei $n$} PL-Zahl
538 \item \alert{Wähle} $\alert{z} = a^nb^n$
539 \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$
540 \item Dann ist $uv^0w \not \in L$
541 \item Damit ist L \alert{nicht} regulär.
542 \end{enumerate}
543 \end{example}
544 \end{frame}
545 }
546
547 \defineUnit{aequivalentezustaende}{%
548 \begin{frame}
549 \frametitle{Äquivalenzen}
550 \setbeamercovered{dynamic}
551
552 \begin{definition}[Äquivalente Worte]
553 Jede Sprache $L \subseteq \Sigma^*$ induziert eine \structure{Äquivalenzrelation $\equiv_L \subseteq \Sigma^* \times \Sigma^*$}
554 \[ u \structure{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right) \]
555 \end{definition}
556
557 \vfill
558
559 \pause
560
561 \begin{definition}[Äquivalente Zustände]
562 Zwei Zustände im DFA $A$ sind \structure{äquivalent} wenn sie die selbe Sprache akzeptieren.
563 \[ p \structure{\equiv_A} q \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{\hat{\delta}(p, w)} \in F \Leftrightarrow \alert{\hat{\delta}(q, w)} \in F \right) \]
564 \end{definition}
565 \end{frame}
566 }
567
568 \defineUnit{unterscheidbarezustaende}{%
569 \begin{frame}
570 \frametitle{Unterscheidbare Zustände}
571 \setbeamercovered{dynamic}
572
573 \begin{definition}[Unterscheidbarkeit]
574 Zwei Zustände sind \structure{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
575 \[ p \structure{\not\equiv_A} q \Longleftrightarrow \left( \exists w \in \Sigma^*. \hat{\delta}(p, w) \alert{\in} F \wedge \hat{\delta}(q, w) \alert{\not\in} F \right) \]
576 \end{definition}
577
578 \begin{theorem}
579 Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$.
580 \end{theorem}
581
582 \pause
583
584 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm]
585 \node[state, initial] (q0) {$q_0$};
586 \node[state] (q1) [right of = q0] {$q_1$};
587 \node[state] (q2) [right of = q1] {$q_2$};
588 \node[state, accepting] (q3) [right of = q2] {$q_3$};
589
590 \draw[->] (q0) edge node {$a$} (q1);
591 \draw[->] (q0) edge [bend left] node {$b$} (q2);
592 \draw[->] (q1) edge node {$a$} (q2);
593 \draw[->] (q1) edge [bend right] node {$b$} (q3);
594 \draw[->] (q2) edge node {$a,b$} (q3);
595 \draw[->] (q3) edge [loop right] node {$a,b$} (q3);
596
597 \node<3>[state, fill=tumred!35] () at (q2) {$q_2$};
598 \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$};
599
600 \node<4>[state, fill=tumred!35] () at (q0) {$q_0$};
601 \node<4>[state, fill=tumred!35] () at (q1) {$q_1$};
602 \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2);
603 \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3);
604 \end{tikzpicture}
605 \end{frame}
606 }
607
608 \defineUnit{quotientenautomat}{%
609 \begin{frame}[t]
610 \frametitle{DFA minimieren}
611 \setbeamercovered{dynamic}
612
613 \begin{block}{Quotientenautomat}
614 \begin{enumerate}
615 \item Entferne alle von $q_0$ \alert{nicht erreichbaren} Zustände
616 \item<1, 3-> Berechne die \alert{unterscheidbaren} Zustände
617 \item<1, 6-> \alert{Kollabiere} die äquivalenten Zustände
618 \end{enumerate}
619 \end{block}
620
621 \vfill
622
623 \begin{columns}[c]<2->
624 \begin{column}{.5\textwidth}<3->
625 \begin{center}
626 \begin{tabu}to .8\textwidth{|X[c]|X[c]|X[c]|X}
627 \multicolumn{2}{l}{0} \\ \tabucline{1-1}
628 \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & \multicolumn{2}{l}{1} \\ \tabucline{1-2}
629 \alt<-4>{}{\textcolor{tumgreen}{$1/a$}} & & \multicolumn{2}{l}{2} \\ \tabucline{1-3}
630 \alt<-3>{}{\textcolor{tumred}{$\times$}} & \alt<-3>{}{\textcolor{tumred}{$\times$}}& \alt<-3>{} {\textcolor{tumred}{$\times$}}& 3 \\ \tabucline{1-3}
631 \end{tabu}
632 \end{center}
633 \end{column}
634 \begin{column}{.5\textwidth}
635 \begin{tikzpicture}[automaton, node distance=2.5cm]
636 \useasboundingbox (-0.5, -0.5) rectangle (2, -2);
637
638 \node[state, initial] (q0) {$q_0$};
639 \node<-5>[state] (q1) [right of = q0] {$q_1$};
640 \node<-5>[state] (q2) [below of = q0] {$q_2$};
641 \node<6>[state, fill=tumred!40] (q12) [right of = q0] {$q_{12}$};
642 \node[state, accepting] (q3) [right of = q2] {$q_3$};
643
644 \draw<-5>[->] (q0) edge node {$a$} (q1);
645 \draw<-5>[->] (q0) edge node {$b$} (q2);
646 \draw<-5>[->] (q1) edge node {$a,b$} (q3);
647 \draw<-5>[->] (q2) edge node {$a,b$} (q3);
648 \draw[->] (q3) edge [loop right] node [above] {$a,b$} (q3);
649
650 \draw<6>[->] (q12) edge node {$a,b$} (q3);
651 \draw<6>[->] (q0) edge node {$a,b$} (q12);
652 \end{tikzpicture}
653 \end{column}
654 \end{columns}
655 \end{frame}
656 }
657
658 \defineUnit{regulaeresprachen}{%
659 \begin{frame}
660 \frametitle{Reguläre Sprachen}
661 \setbeamercovered{dynamic}
662
663 \begin{center}
664 \begin{tikzpicture}[node distance=2cm]
665 \node (nfa) {NFA};
666 \node (dfa) [left of=nfa] {DFA};
667 \node (enfa) [right of=nfa] {$\epsilon$-NFA};
668 \node (re) [below of=nfa] {RE};
669
670 \draw [every edge] (nfa) -- (dfa);
671 \draw [every edge] (enfa) -- (nfa);
672 \draw [every edge] (dfa) -- (re);
673 \draw [every edge] (nfa) -- (re);
674 \draw [every edge] (re) -- (enfa);
675 \end{tikzpicture}
676 \end{center}
677
678 \vfill
679
680 \begin{theorem}
681 Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
682 \vspace{1em}
683 \begin{description}
684 \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
685 \item[Leerheitsproblem] Ist $L(D) = \emptyset$?
686 \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
687 \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$?
688 \end{description}
689 \end{theorem}
690 \end{frame}
691 }