Mercurial > 13ss.theoinf
annotate notes/tex/ue02_notes.tex @ 11:20c64dea84fa
missing edge
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 30 Apr 2013 02:17:20 +0200 |
| parents | 5fc4bbf3ecc3 |
| children | 90ffda7e20c7 |
| rev | line source |
|---|---|
| 8 | 1 \documentclass[compress, german, t]{beamer} |
| 2 | |
| 3 \usepackage[ngerman,english]{babel} | |
| 4 \uselanguage{German} | |
| 5 \languagepath{German} | |
| 6 | |
| 7 \usepackage[T1]{fontenc} | |
| 8 \usepackage[utf8]{inputenc} | |
| 9 | |
| 10 \usepackage{helvet} | |
| 11 \usepackage{url} | |
| 12 \usepackage{listings} | |
| 13 \usepackage{xcolor} | |
| 14 \usepackage{tikz} | |
| 15 \usepackage{pgfplots} | |
| 16 \usetikzlibrary{automata} | |
| 17 \usetikzlibrary{calc} | |
| 18 \usetikzlibrary{shapes.geometric} | |
| 19 \usetikzlibrary{positioning} | |
| 20 \usepackage{tabu} | |
| 21 | |
| 22 \usepackage{beamerthemeLEA2} | |
| 23 | |
| 24 \newcommand{\N} {\mathbb{N}} % natürliche Zahlen | |
| 25 \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen | |
| 26 \newcommand{\R} {\mathbb{R}} % reelle Zahlen | |
| 27 \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit | |
| 28 \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole) | |
| 29 \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} | |
| 30 | |
| 31 \tikzstyle{every edge} = [draw,very thick,->,>=latex] | |
| 32 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10] | |
| 33 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] | |
| 34 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] | |
| 35 | |
| 36 \title{Übung 2: Konversion RE $\rightarrow$ DFA} | |
| 37 \subtitle{Theoretische Informatik Sommersemester 2013} | |
| 38 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} | |
| 39 | |
| 40 \begin{document} | |
| 41 | |
| 42 \begin{frame} | |
| 43 \titlepage | |
| 44 \end{frame} | |
| 45 | |
| 46 \begin{frame} | |
| 47 \setbeamercovered{dynamic} | |
| 48 \frametitle{Reguläre Ausdrücke} | |
| 49 | |
| 50 \begin{definition}[Regulärer Ausdruck] | |
| 51 \alert{Reguläre Ausdrücke} sind induktiv definiert | |
| 52 \begin{itemize} | |
| 53 \item \alert{$\emptyset$} ist ein regulärer Ausdruck | |
| 54 \item \alert{$\epsilon$} ist ein regulärer Ausdruck | |
| 55 \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck | |
| 56 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch | |
| 57 \begin{description} | |
| 58 \item[Konkatenation] \alert{$\alpha\beta$} | |
| 59 \item[Veroderung] \alert{$\alpha \mid \beta$} | |
| 60 \item[Wiederholung] \alert{$\alpha^*$} | |
| 61 \end{description} | |
| 62 \end{itemize} | |
| 63 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$ | |
| 64 \end{definition} | |
| 65 | |
| 66 \begin{example} | |
| 67 $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$ | |
| 68 \end{example} | |
| 69 \end{frame} | |
| 70 | |
| 71 \begin{frame}[c] | |
| 72 \setbeamercovered{dynamic} | |
| 73 \frametitle{Konversionen} | |
| 74 | |
| 75 \begin{center} | |
| 76 \begin{tikzpicture}[node distance=2cm] | |
| 77 \node (nfa) {NFA}; | |
| 78 \node (dfa) [left of=nfa] {DFA}; | |
| 79 \node (enfa) [right of=nfa] {$\epsilon$-NFA}; | |
| 80 \node (re) [below of=nfa] {RE}; | |
| 81 | |
| 82 \draw [every edge, tumred] (nfa) -- (dfa); | |
| 83 \draw [every edge, tumred] (enfa) -- (nfa); | |
| 84 \draw [every edge] (dfa) -- (re); | |
| 85 \draw [every edge] (nfa) -- (re); | |
| 86 \draw [every edge, tumred] (re) -- (enfa); | |
| 87 \end{tikzpicture} | |
| 88 \end{center} | |
| 89 \end{frame} | |
| 90 | |
| 91 \begin{frame} | |
| 92 \setbeamercovered{dynamic} | |
| 93 \frametitle{RE $\rightarrow$ $\epsilon$-NFA} | |
| 94 | |
| 95 \begin{block}{Idee (Kleene)} | |
| 96 Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert. | |
| 97 \end{block} | |
| 98 | |
| 99 \begin{tabu} to \linewidth {XXX} | |
| 100 \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\ | |
| 101 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] | |
| 102 \node[state, initial] () {}; | |
| 103 \end{tikzpicture} & | |
| 104 | |
| 105 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] | |
| 106 \node[state, initial, accepting] () {}; | |
| 107 \end{tikzpicture} & | |
| 108 | |
| 109 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] | |
| 110 \node[state, initial] (i) {}; | |
| 111 \node[state, accepting] (j) [right of=i] {}; | |
| 112 | |
| 113 \draw[->] (i) edge node {$a$} (j); | |
| 114 \end{tikzpicture} \\ | |
| 115 \vspace{2em} | |
| 116 \alert{$\gamma = \alpha\beta$} \\ | |
| 117 \multicolumn3{c}{ | |
| 118 \begin{tikzpicture}[automaton, small] | |
| 119 \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1); | |
| 120 \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$}; | |
| 121 | |
| 122 \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1); | |
| 123 \node[tumgreen] () at (4.75, -1.2) {$N_\beta$}; | |
| 124 | |
| 125 \node[state, initial] (i) at (0, 0) {}; | |
| 126 \node[state] (j) at (1.5, 0.5) {}; | |
| 127 \node[state] (k) at (1.5, -0.5) {}; | |
| 128 \node[state] (l) at (4, 0) {}; | |
| 129 \node[state, accepting] (m) at (5.5, 0) {}; | |
| 130 | |
| 131 \draw[->] (j) edge node {$\epsilon$} (l); | |
| 132 \draw[->] (k) edge node {$\epsilon$} (l); | |
| 133 \end{tikzpicture} | |
| 134 }\\ | |
| 135 \end{tabu} | |
| 136 \end{frame} | |
| 137 | |
| 138 \begin{frame} | |
| 139 \setbeamercovered{dynamic} | |
| 140 \frametitle{RE $\rightarrow$ $\epsilon$-NFA} | |
| 141 | |
| 142 \begin{tabu} to \linewidth {X} | |
| 143 \alert{$\gamma = \alpha \mid \beta$} \\ | |
| 144 \centering | |
| 145 \begin{tikzpicture}[automaton, small] | |
| 146 \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5); | |
| 147 \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$}; | |
| 148 | |
| 149 \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5); | |
| 150 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$}; | |
| 151 | |
| 152 \node[state, initial] (i) at (0, 0) {}; | |
| 153 | |
| 154 \node[state] (j) at (2.5, 1) {}; | |
| 155 \node[state, accepting] (k) at (4, 1) {}; | |
| 156 \node[state] (l) at (2.5, -1) {}; | |
| 157 \node[state, accepting] (m) at (4, -1) {}; | |
| 158 | |
| 159 \draw[->] (i) edge node {$\epsilon$} (j); | |
| 160 \draw[->] (i) edge node {$\epsilon$} (l); | |
| 161 \end{tikzpicture} \\ | |
| 162 \vfill | |
| 163 | |
| 164 \alert{$\gamma = \alpha^*$} \\ | |
| 165 \centering | |
| 166 \begin{tikzpicture}[automaton, small, bend angle=70] | |
| 167 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1); | |
| 168 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$}; | |
| 169 | |
|
10
5fc4bbf3ecc3
missing accepting state
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
8
diff
changeset
|
170 \node[state, initial, accepting] (i) at (0, 0) {}; |
| 8 | 171 |
| 172 \node[state] (j) at (2.5, 0) {}; | |
| 173 \node[state, accepting] (k) at (4, 0.5) {}; | |
| 174 \node[state, accepting] (m) at (4, -0.5) {}; | |
| 175 | |
| 176 \draw[->] (i) edge node {$\epsilon$} (j); | |
| 177 \draw[->] (k) edge [bend right] node {$\epsilon$} (j); | |
| 178 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j); | |
| 179 \end{tikzpicture} | |
| 180 \end{tabu} | |
| 181 \end{frame} | |
| 182 | |
| 183 \begin{frame} | |
| 184 \setbeamercovered{dynamic} | |
| 185 \frametitle{$\epsilon$-NFA $\rightarrow$ NFA} | |
| 186 | |
| 187 \begin{block}{Idee} | |
| 188 Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen. | |
| 189 \begin{enumerate} | |
| 190 \item<1-> Entferne \alert{unnötige Knoten}. | |
| 191 \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. | |
| 192 \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten. | |
| 193 \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand. | |
| 194 \end{enumerate} | |
| 195 \end{block} | |
| 196 | |
| 197 \vfill | |
| 198 | |
| 199 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm] | |
| 200 \useasboundingbox (-1.4,2) rectangle (9, -2); | |
| 201 | |
| 202 \node<-4>[state, initial] (q0) {$q_0$}; | |
| 203 \node[state] (q2) [right = 3.2cm of q0] {$q_2$}; | |
| 204 \node[state] (q3) [right of = q2] {$q_3$}; | |
| 205 \node[state, accepting] (q4) [right of = q3] {$q_4$}; | |
| 206 | |
| 207 \draw[->] (q2) edge node {$0$} (q3); | |
| 208 \draw[->] (q3) edge node {$1$} (q4); | |
| 209 | |
| 210 \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2); | |
| 211 \draw[->] (q4) edge [bend right] node [above] {$1$} (q3); | |
| 212 \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); | |
| 213 | |
| 214 \node<1>[state] (q1) [right of = q0] {$q_1$}; | |
| 215 \draw<1>[->] (q0) edge node {$\epsilon$} (q1); | |
| 216 \draw<1>[->] (q1) edge node {$1$} (q2); | |
| 217 | |
| 218 \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$}; | |
| 219 \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1); | |
| 220 \draw<2>[->, tumred] (q1) edge node {$0$} (q2); | |
| 221 \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2); | |
| 222 | |
| 223 \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); | |
| 224 \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3); | |
| 225 \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2); | |
| 226 \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2); | |
| 227 | |
| 228 \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2); | |
| 229 \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3); | |
| 11 | 230 \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3); |
| 8 | 231 \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2); |
| 232 | |
| 233 \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$}; | |
| 234 | |
| 235 \node<6->[state, initial, accepting] (q0) {$q_0$}; | |
| 236 \end{tikzpicture} | |
| 237 \end{frame} | |
| 238 | |
| 239 \begin{frame} | |
| 240 \setbeamercovered{dynamic} | |
| 241 \frametitle{NFA $\rightarrow$ DFA} | |
| 242 | |
| 243 \begin{block}{Idee (Potenzmengenkonstruktion)} | |
| 244 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)$}. | |
| 245 | |
| 246 \begin{itemize} | |
| 247 \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \mapsto P(Q)$ \\ | |
| 248 \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\] | |
| 249 \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$ | |
| 250 \end{itemize} | |
| 251 \end{block} | |
| 252 | |
| 253 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm] | |
| 254 \useasboundingbox (-1.4,2) rectangle (9, -2); | |
| 255 | |
| 256 \node[state, initial] (q0) {$q_0$}; | |
| 257 \node[state, accepting] (q1) [right of = q0] {$q_1$}; | |
| 258 | |
| 259 \draw[->] (q0) edge [loop above] node {$0,1$} (q0); | |
| 260 \draw[->] (q0) edge node {$1$} (q1); | |
| 261 | |
| 262 \node<2->(sep) [right of = q1] {$\rightarrow$}; | |
| 263 | |
| 264 \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$}; | |
| 265 | |
| 266 \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$}; | |
| 267 \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0); | |
| 268 \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01); | |
| 269 | |
| 270 \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01); | |
| 271 \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0); | |
| 272 | |
| 273 \end{tikzpicture} | |
| 274 \end{frame} | |
| 275 | |
| 276 \begin{frame} | |
| 277 \setbeamercovered{dynamic} | |
| 278 \frametitle{Produktautomat} | |
| 279 \begin{theorem} | |
| 280 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} | |
| 281 | |
| 282 \begin{align*} | |
| 283 M &:= (\alert{Q_1 \times Q_2}, \Sigma, \delta, (s_1, s_2), F_1 \times F_2) \\ | |
| 284 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right) | |
| 285 \end{align*} | |
| 286 | |
| 287 ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert. | |
| 288 \end{theorem} | |
| 289 | |
| 290 \end{frame} | |
| 291 | |
| 292 \end{document} |