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