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