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