Mercurial > 13ss.theoinf

comparison notes/tex/automatons.tex @ 41:5d10471f5585

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
move frame-definitions out of presentations
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 20:42:36 +0200
parents
children 35e8bb96da7b
comparison
equal deleted inserted replaced
40:3175d3871752 41:5d10471f5585
1 \defineUnit{dfa}{%
2 \begin{frame}
3 \frametitle{DFA}
4
5 \begin{definition}[Deterministischer endlicher Automat]
6 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
7 \begin{itemize}
8 \item endlichen Menge von \alert{Zuständen} $Q$
9 \item endlichen \alert{Eingabealphabet} $\Sigma$
10 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$
11 \item \alert{Startzustand} $q_0 \in Q$
12 \item Menge von \alert{Endzuständen} $F \subseteq Q$
13 \end{itemize}
14 \end{definition}
15
16 \vfill
17 \pause
18
19 \begin{center}
20 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
21 \node[state, initial] (q0) {$q_0$};
22 \node[state, accepting] (q1) [right of = q0] {$q_1$};
23 \node[state] (q2) [right of = q1] {$q_2$};
24
25 \draw[->] (q0) edge [loop above] node {0} (q0);
26 \draw[->] (q2) edge [loop above] node {1} (q2);
27 \draw[->] (q0) edge [bend left] node {1} (q1);
28 \draw[->] (q1) edge [bend left] node {1} (q0);
29 \draw[->] (q1) edge [bend left] node {0} (q2);
30 \draw[->] (q2) edge [bend left] node {0} (q1);
31 \end{tikzpicture}
32 \end{center}
33 \end{frame}
34 }
35
36 \defineUnit{nfa}{%
37 \begin{frame}
38 \frametitle{NFA}
39 \begin{definition}[Nicht-Deterministischer endlicher Automat]
40 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
41 \begin{itemize}
42 \item $Q, \Sigma, q_0, F$ wie ein DFA
43 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$
44 \end{itemize}
45 \end{definition}
46
47 \vfill
48 \pause
49
50 \begin{center}
51 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
52 \node[state, initial] (q0) {$q_0$};
53 \node[state, accepting] (q1) [right of = q0] {$q_1$};
54 \draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame}
55 }
56
57 \defineUnit{enfa}{%
58 \begin{frame}
59 \frametitle{$\epsilon$-NFA}
60 \begin{definition}[NFA mit $\epsilon$-Übergängen]
61 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
62 \begin{itemize}
63 \item $Q, \Sigma, q_0, F$ wie ein DFA
64 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$
65 \end{itemize}
66 \end{definition}
67
68 \vfill
69 \pause
70
71 \begin{center}
72 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]
73 \node[state] (q1) {$q_1$};
74 \node[state, initial] (q0) [left of = q1] {$q_0$};
75 \node[state, accepting] (q2) [right of = q1] {$q_2$};
76 \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}
77 }
78
79 \defineUnit{endlicheautomaten}{%
80 \begin{frame}
81 \frametitle{Endliche Automaten}
82 \begin{block}{Übergangsfunktionen}
83 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
84
85 \begin{description}
86 \item[DFA] $\delta : Q \times \Sigma \to Q$
87 \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$
88 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$
89 \end{description}
90 \end{block}
91
92 \vfill
93
94 \begin{theorem}
95 \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln.
96 \end{theorem}
97 \end{frame}
98 }
99
100 \defineUnit{regex}{%
101 \begin{frame}
102 \frametitle{Reguläre Ausdrücke}
103 \setbeamercovered{dynamic}
104
105 \begin{definition}[Regulärer Ausdruck]
106 \alert{Reguläre Ausdrücke} sind induktiv definiert
107 \begin{itemize}
108 \item \alert{$\emptyset$} ist ein regulärer Ausdruck
109 \item \alert{$\epsilon$} ist ein regulärer Ausdruck
110 \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck
111 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch
112 \begin{description}
113 \item[Konkatenation] \alert{$\alpha\beta$}
114 \item[Veroderung] \alert{$\alpha \mid \beta$}
115 \item[Wiederholung] \alert{$\alpha^*$}
116 \end{description}
117 \end{itemize}
118 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$
119 \end{definition}
120
121 \begin{example}
122 $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$
123 \end{example}
124 \end{frame}
125 }
126
127 \defineUnit{automatenkonversionen}{%
128 \begin{frame}[c]
129 \frametitle{Konversionen}
130 \setbeamercovered{dynamic}
131
132 \begin{center}
133 \begin{tikzpicture}[node distance=2cm]
134 \node (nfa) {NFA};
135 \node (dfa) [left of=nfa] {DFA};
136 \node (enfa) [right of=nfa] {$\epsilon$-NFA};
137 \node (re) [below of=nfa] {RE};
138
139 \draw [every edge, tumred] (nfa) -- (dfa);
140 \draw [every edge, tumred] (enfa) -- (nfa);
141 \draw [every edge] (dfa) -- (re);
142 \draw [every edge] (nfa) -- (re);
143 \draw [every edge, tumred] (re) -- (enfa);
144 \end{tikzpicture}
145 \end{center}
146 \end{frame}
147 }
148
149 \defineUnit{rezunfa}{%
150 \begin{frame}
151 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
152 \setbeamercovered{dynamic}
153
154 \begin{block}{Idee (Kleene)}
155 Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert.
156 \end{block}
157
158 \begin{tabu} to \linewidth {XXX}
159 \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\
160 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
161 \node[state, initial] () {};
162 \end{tikzpicture} &
163
164 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
165 \node[state, initial, accepting] () {};
166 \end{tikzpicture} &
167
168 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)]
169 \node[state, initial] (i) {};
170 \node[state, accepting] (j) [right of=i] {};
171
172 \draw[->] (i) edge node {$a$} (j);
173 \end{tikzpicture} \\
174 \vspace{2em}
175 \alert{$\gamma = \alpha\beta$} \\
176 \multicolumn3{c}{
177 \begin{tikzpicture}[automaton, small]
178 \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1);
179 \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$};
180
181 \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1);
182 \node[tumgreen] () at (4.75, -1.2) {$N_\beta$};
183
184 \node[state, initial] (i) at (0, 0) {};
185 \node[state] (j) at (1.5, 0.5) {};
186 \node[state] (k) at (1.5, -0.5) {};
187 \node[state] (l) at (4, 0) {};
188 \node[state, accepting] (m) at (5.5, 0) {};
189
190 \draw[->] (j) edge node {$\epsilon$} (l);
191 \draw[->] (k) edge node {$\epsilon$} (l);
192 \end{tikzpicture}
193 }\\
194 \end{tabu}
195 \end{frame}
196 }
197
198 \defineUnit{rezuenfabeispiel}{%
199 \begin{frame}
200 \frametitle{RE $\rightarrow$ $\epsilon$-NFA}
201 \setbeamercovered{dynamic}
202
203 \begin{tabu} to \linewidth {X}
204 \alert{$\gamma = \alpha \mid \beta$} \\
205 \centering
206 \begin{tikzpicture}[automaton, small]
207 \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5);
208 \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$};
209
210 \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5);
211 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$};
212
213 \node[state, initial] (i) at (0, 0) {};
214
215 \node[state] (j) at (2.5, 1) {};
216 \node[state, accepting] (k) at (4, 1) {};
217 \node[state] (l) at (2.5, -1) {};
218 \node[state, accepting] (m) at (4, -1) {};
219
220 \draw[->] (i) edge node {$\epsilon$} (j);
221 \draw[->] (i) edge node {$\epsilon$} (l);
222 \end{tikzpicture} \\
223 \vfill
224
225 \alert{$\gamma = \alpha^*$} \\
226 \centering
227 \begin{tikzpicture}[automaton, small, bend angle=70]
228 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1);
229 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$};
230
231 \node[state, initial, accepting] (i) at (0, 0) {};
232
233 \node[state] (j) at (2.5, 0) {};
234 \node[state, accepting] (k) at (4, 0.5) {};
235 \node[state, accepting] (m) at (4, -0.5) {};
236
237 \draw[->] (i) edge node {$\epsilon$} (j);
238 \draw[->] (k) edge [bend right] node {$\epsilon$} (j);
239 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j);
240 \end{tikzpicture}
241 \end{tabu}
242 \end{frame}
243 }
244
245 \defineUnit{enfazunfa}{%
246 \begin{frame}
247 \frametitle{$\epsilon$-NFA $\rightarrow$ NFA}
248 \setbeamercovered{dynamic}
249
250 \begin{block}{Idee}
251 Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen.
252 \begin{enumerate}
253 \item<1-> Entferne \alert{unnötige Knoten}.
254 \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.
255 \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten.
256 \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand.
257 \end{enumerate}
258 \end{block}
259
260 \vfill
261
262 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm]
263 \useasboundingbox (-1.4,2) rectangle (9, -2);
264
265 \node<-4>[state, initial] (q0) {$q_0$};
266 \node[state] (q2) [right = 3.2cm of q0] {$q_2$};
267 \node[state] (q3) [right of = q2] {$q_3$};
268 \node[state, accepting] (q4) [right of = q3] {$q_4$};
269
270 \draw[->] (q2) edge node {$0$} (q3);
271 \draw[->] (q3) edge node {$1$} (q4);
272
273 \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
274 \draw[->] (q4) edge [bend right] node [above] {$1$} (q3);
275 \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
276
277 \node<1>[state] (q1) [right of = q0] {$q_1$};
278 \draw<1>[->] (q0) edge node {$\epsilon$} (q1);
279 \draw<1>[->] (q1) edge node {$1$} (q2);
280
281 \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$};
282 \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1);
283 \draw<2>[->, tumred] (q1) edge node {$0$} (q2);
284 \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2);
285
286 \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4);
287 \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3);
288 \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2);
289 \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2);
290
291 \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2);
292 \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3);
293 \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3);
294 \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2);
295
296 \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$};
297
298 \node<6->[state, initial, accepting] (q0) {$q_0$};
299 \end{tikzpicture}
300 \end{frame}
301 }
302
303 \defineUnit{nfazudfa}{%
304 \begin{frame}
305 \frametitle{NFA $\rightarrow$ DFA}
306 \setbeamercovered{dynamic}
307
308 \begin{block}{Idee (Potenzmengenkonstruktion)}
309 Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}.
310
311 \begin{itemize}
312 \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\
313 \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\]
314 \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$
315 \end{itemize}
316 \end{block}
317
318 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm]
319 \useasboundingbox (-1.4,2) rectangle (9, -2);
320
321 \node[state, initial] (q0) {$q_0$};
322 \node[state, accepting] (q1) [right of = q0] {$q_1$};
323
324 \draw[->] (q0) edge [loop above] node {$0,1$} (q0);
325 \draw[->] (q0) edge node {$1$} (q1);
326
327 \node<2->(sep) [right of = q1] {$\rightarrow$};
328
329 \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$};
330
331 \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$};
332 \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0);
333 \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01);
334
335 \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01);
336 \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0);
337
338 \end{tikzpicture}
339 \end{frame}
340 }
341
342 \defineUnit{produktautomat}{%
343 \begin{frame}
344 \frametitle{produktautomat}
345 \setbeamercovered{dynamic}
346 \begin{theorem}
347 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}
348
349 \begin{align*}
350 m &:= (\alert{q_1 \times q_2}, \sigma, \delta, (s_1, s_2), f_1 \times f_2) \\
351 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right)
352 \end{align*}
353
354 ein dfa, der $l(m_1) \cap l(m_2)$ akzeptiert.
355 \end{theorem}
356 \end{frame}
357 }
358
359 \defineUnit{regexrechnen}{%
360 \begin{frame}
361 \frametitle{Nochmal Reguläre Ausdrücke}
362 \setbeamercovered{dynamic}
363
364 \begin{theorem}
365 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$.
366
367 \begin{itemize}
368 \item \alert{Assoziative} Operationen
369 \item Veroderung \alert{kommutativ}
370 \item \alert{Distributivität}: $\alpha (\beta \mid \gamma) \equiv \alpha\beta \mid \alpha\gamma$
371 \item $\emptyset$ \alert{neutral} bezüglich Oder
372 \item $\epsilon$ \alert{neutral} bezüglich Konkatenation
373 \end{itemize}
374 \end{theorem}
375
376 \begin{example}
377 \[
378 1\psi \mid 0\phi \mid \psi \equiv 0 \phi \mid (1 \mid \epsilon) \psi
379 \]
380 \end{example}
381 \end{frame}
382 }
383
384 \defineUnit{arden}{%
385 \begin{frame}
386 \frametitle{Ardens Lemma}
387 \setbeamercovered{dynamic}
388
389 \begin{theorem}[Ardens Lemma]
390 Sind $A$, $B$ und $X$ Sprachen mit $\epsilon \not \in A$, dann gilt
391 \[
392 X = AX \cup B \Longrightarrow X = A^* B
393 \]
394 Speziell gilt für reguläre Ausdrücke
395 \[
396 X \equiv \alpha X \mid \beta \Longrightarrow X \equiv \alpha^* \beta
397 \]
398 \end{theorem}
399
400 \begin{example}
401 \[
402 \psi \equiv 0 \psi \mid (1 \mid \epsilon) \phi \Longrightarrow \psi \equiv 0^*(1\mid \epsilon) \phi
403 \]
404 \end{example}
405 \end{frame}
406 }
407
408 \defineUnit{nfazure}{%
409 \begin{frame}
410 \frametitle{NFA $\rightarrow$ RE}
411 \setbeamercovered{dynamic}
412
413 \begin{block}{Idee}
414 Erzeuge ein Gleichungssystem aus allen Zuständen.
415 \begin{enumerate}
416 \item<1,2-> Ausdruck für jeden Zustand
417 \item<1,3-> Auflösen nach $X_0$ mit Algebra und Ardens Lemma
418 \end{enumerate}
419 \end{block}
420 \begin{columns}<2->
421 \begin{column}[b]{.65\textwidth}
422 \begin{align*}
423 X_0 &\equiv 1X_0 \mid 0X_1 \\
424 &\equiv \uncover<4->{1X_0 \mid 00^*(\epsilon \mid 1X_0)} \\
425 &\equiv \uncover<4->{(1 \mid 00^*1) X_0 \mid 00^*} \\
426 &\equiv \uncover<4->{(1 \mid 00^*1)^*(00^*)} \\
427 \\
428 X_1 &\equiv 1X_0 \mid 0X_1 \alt<3->{\mid \epsilon}{\alert{\mid \epsilon}} \\
429 &\equiv \uncover<3-> {0X_1 \mid (\epsilon \mid 1 X_0)}\\
430 &\equiv \uncover<3-> {\alt<-2,4->{0^*(\epsilon \mid 1X_0)}{\alert{0^*(\epsilon \mid 1X_0)}}}
431 \end{align*}
432 \end{column}
433 \begin{column}[t]{.35\textwidth}
434 \begin{tikzpicture}[automaton]
435 \node[state, initial] (q0) {$q_0$};
436 \node[state, accepting] (q1) [below of=q0] {$q_1$};
437
438 \draw[->] (q0) edge [bend right] node [left] {$0$} (q1);
439 \draw[->] (q1) edge [bend right] node [right] {$1$} (q0);
440 \draw[->] (q0) edge [loop right] node {$1$} (q0);
441 \draw[->] (q1) edge [loop right] node {$0$} (q1);
442 \end{tikzpicture}
443 \end{column}
444 \end{columns}
445 \end{frame}
446 }
447
448 \defineUnit{rpl}{%
449 \begin{frame}
450 \frametitle{Pumping Lemma}
451 \setbeamercovered{dynamic}
452
453 \begin{theorem}[Pumping Lemma für reguläre Sprachen]
454 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
455 \begin{itemize}
456 \item $v \neq \epsilon$
457 \item $|uv| \alert{\leq n}$
458 \item $\forall i \alert{\geq 0}. uv^iw \in R$
459 \end{itemize}
460 \end{theorem}
461
462 \vfill
463
464 \begin{center}
465 \begin{tikzpicture}[automaton]
466 \node[state, initial] (q0) {};
467 \node[state, fill=tumred!20] (q1) [right of=q0] {};
468 \node[state, accepting] (q2) [right of=q1] {};
469
470 \draw[->, densely dashed] (q0) edge node {$u$} (q1);
471 \draw[->, tumred] (q1) edge [loop above] node {$v$} (q1);
472 \draw[->, densely dashed] (q1) edge node {$w$} (q2);
473 \end{tikzpicture}
474 \end{center}
475 \end{frame}
476 }
477
478 \defineUnit{rplanwenden}{%
479 \begin{frame}
480 \frametitle{Nichtregularität beweisen}
481 \setbeamercovered{dynamic}
482
483 \begin{block}{Idee}
484 Gegenbeispiel fürs Pumpinglemma suchen.
485 \[
486 \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}
487 \]
488 \end{block}
489
490 \vfill
491
492 \begin{example}<2->
493 Ist $L = \left\{ a^ib^i \mid i \in \N_0 \right\}$ regulär?
494 \begin{enumerate}
495 \item \alert{Sei $n$} PL-Zahl
496 \item \alert{Wähle} $\alert{z} = a^nb^n$
497 \item Dann ist \alert{$z = uvw$} mit \alert{$|uv| \leq n$}, hier: $v=a^k$ mit $k > 0$
498 \item Dann ist $uv^0w \not \in L$
499 \item Damit ist L \alert{nicht} regulär.
500 \end{enumerate}
501 \end{example}
502 \end{frame}
503 }
504
505 \defineUnit{aequivalenteZustaende}{%
506 \begin{frame}
507 \frametitle{Äquivalenzen}
508 \setbeamercovered{dynamic}
509
510 \begin{definition}[Äquivalente Worte]
511 Jede Sprache $L \subseteq \Sigma^*$ induziert eine Äquivalenzrelation $\alert{\equiv_L \subseteq \Sigma^* \times \Sigma^*}$:
512 \[
513 u \alert{\equiv_L} v \Longleftrightarrow \left( \forall w \in \Sigma^*. \alert{uw} \in L \Leftrightarrow \alert{vw} \in L\right)
514 \]
515 \end{definition}
516
517 \vfill
518
519 \pause
520
521 \begin{definition}[Äquivalente Zustände]
522 Zwei Zustände im DFA $A$ sind \alert{äquivalent} wenn sie die selbe Sprache akzeptieren.
523
524 \[
525 p \alert{\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)
526 \]
527 \end{definition}
528 \end{frame}
529 }
530
531 \defineUnit{unterscheidbareZustaende}{%
532 \begin{frame}
533 \frametitle{Unterscheidbare Zustände}
534 \setbeamercovered{dynamic}
535
536 \begin{definition}[Unterscheidbarkeit]
537 Zwei Zustände sind \alert{unterscheidbar}, wenn sie unterschiedliche Sprachen akzeptieren.
538 \[
539 p \alert{\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)
540 \]
541 \end{definition}
542
543 \begin{theorem}
544 Sind $\delta(p, a)$ und $\delta(q, a)$ unterscheidbar, dann auch $p$ und $q$.
545 \end{theorem}
546
547 \pause
548
549 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.5cm]
550 \node[state, initial] (q0) {$q_0$};
551 \node[state] (q1) [right of = q0] {$q_1$};
552 \node[state] (q2) [right of = q1] {$q_2$};
553 \node[state, accepting] (q3) [right of = q2] {$q_3$};
554
555 \draw[->] (q0) edge node {$a$} (q1);
556 \draw[->] (q0) edge [bend left] node {$b$} (q2);
557 \draw[->] (q1) edge node {$a$} (q2);
558 \draw[->] (q1) edge [bend right] node {$b$} (q3);
559 \draw[->] (q2) edge node {$a,b$} (q3);
560 \draw[->] (q3) edge [loop right] node {$a,b$} (q3);
561
562 \node<3>[state, fill=tumred!35] () at (q2) {$q_2$};
563 \node<3->[state, accepting, fill=tumgreen!35] () at (q3) {$q_3$};
564
565 \node<4>[state, fill=tumred!35] () at (q0) {$q_0$};
566 \node<4>[state, fill=tumred!35] () at (q1) {$q_1$};
567 \draw<4>[->, tumred] (q0) edge [bend left] node {$b$} (q2);
568 \draw<4>[->, tumgreen] (q1) edge [bend right] node {$b$} (q3);
569 \end{tikzpicture}
570 \end{frame}
571 }