Mercurial > 13ss.theoinf
comparison notes/tex/ue02_notes.tex @ 44:15351d87ce76
transition notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 22:06:26 +0200 |
parents | 27fedbbdab6d |
children |
comparison
equal
deleted
inserted
replaced
43:c14b92bfa07f | 44:15351d87ce76 |
---|---|
1 \input{preamble.tex} | 1 \input{preamble.tex} |
2 \input{frames.tex} | |
2 | 3 |
3 \title{Übung 2: Konversion RE $\rightarrow$ DFA} | 4 \title{Übung 2: Konversion RE $\rightarrow$ DFA} |
4 \subtitle{Theoretische Informatik Sommersemester 2013} | 5 \subtitle{Theoretische Informatik Sommersemester 2013} |
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} | 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
6 | 7 |
7 \begin{document} | 8 \begin{document} |
8 | 9 \showUnit{titel} |
9 \begin{frame} | 10 \showUnit{regex} |
10 \titlepage | 11 \showUnit{rezuenfa} |
11 \end{frame} | 12 \showUnit{rezuenfazwei} |
12 | 13 \showUnit{enfazunfa} |
13 \begin{frame} | 14 \showUnit{nfazudfa} |
14 \setbeamercovered{dynamic} | 15 \showUnit{produktautomat} |
15 \frametitle{Reguläre Ausdrücke} | |
16 | |
17 \begin{definition}[Regulärer Ausdruck] | |
18 \alert{Reguläre Ausdrücke} sind induktiv definiert | |
19 \begin{itemize} | |
20 \item \alert{$\emptyset$} ist ein regulärer Ausdruck | |
21 \item \alert{$\epsilon$} ist ein regulärer Ausdruck | |
22 \item Für alle $a \in \Sigma$ ist \alert{$a$} ein regulärer Ausdruck | |
23 \item Sind $\alpha$ und $\beta$ reguläre Ausdrücke, dann auch | |
24 \begin{description} | |
25 \item[Konkatenation] \alert{$\alpha\beta$} | |
26 \item[Veroderung] \alert{$\alpha \mid \beta$} | |
27 \item[Wiederholung] \alert{$\alpha^*$} | |
28 \end{description} | |
29 \end{itemize} | |
30 Analoge Sprachdefinition, z.b. $L(\alpha\beta) = L(\alpha)L(\beta)$ | |
31 \end{definition} | |
32 | |
33 \begin{example} | |
34 $\alpha = (0|1)^*00$ \hfill $L(\alpha) = \left\{x \mid x \text{ Binärzahl}, x \mod 4 = 0 \right\}$ | |
35 \end{example} | |
36 \end{frame} | |
37 | |
38 \begin{frame}[c] | |
39 \setbeamercovered{dynamic} | |
40 \frametitle{Konversionen} | |
41 | |
42 \begin{center} | |
43 \begin{tikzpicture}[node distance=2cm] | |
44 \node (nfa) {NFA}; | |
45 \node (dfa) [left of=nfa] {DFA}; | |
46 \node (enfa) [right of=nfa] {$\epsilon$-NFA}; | |
47 \node (re) [below of=nfa] {RE}; | |
48 | |
49 \draw [every edge, tumred] (nfa) -- (dfa); | |
50 \draw [every edge, tumred] (enfa) -- (nfa); | |
51 \draw [every edge] (dfa) -- (re); | |
52 \draw [every edge] (nfa) -- (re); | |
53 \draw [every edge, tumred] (re) -- (enfa); | |
54 \end{tikzpicture} | |
55 \end{center} | |
56 \end{frame} | |
57 | |
58 \begin{frame} | |
59 \setbeamercovered{dynamic} | |
60 \frametitle{RE $\rightarrow$ $\epsilon$-NFA} | |
61 | |
62 \begin{block}{Idee (Kleene)} | |
63 Für einen Ausdruck \alert{$\gamma$} wird rekursiv mit struktureller Induktion ein $\epsilon$-NFA konstruiert. | |
64 \end{block} | |
65 | |
66 \begin{tabu} to \linewidth {XXX} | |
67 \alert{$\gamma = \emptyset$} & \alert{$\gamma = \epsilon$} & \alert{$\gamma = a \in \Sigma$} \\ | |
68 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] | |
69 \node[state, initial] () {}; | |
70 \end{tikzpicture} & | |
71 | |
72 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] | |
73 \node[state, initial, accepting] () {}; | |
74 \end{tikzpicture} & | |
75 | |
76 \begin{tikzpicture}[automaton, small, baseline=(current bounding box.north)] | |
77 \node[state, initial] (i) {}; | |
78 \node[state, accepting] (j) [right of=i] {}; | |
79 | |
80 \draw[->] (i) edge node {$a$} (j); | |
81 \end{tikzpicture} \\ | |
82 \vspace{2em} | |
83 \alert{$\gamma = \alpha\beta$} \\ | |
84 \multicolumn3{c}{ | |
85 \begin{tikzpicture}[automaton, small] | |
86 \draw[tumgreen, fill=tumgreen!20] (-0.3, 1) rectangle (1.8, -1); | |
87 \node[tumgreen] () at (0.75, -1.2) {$N_\alpha$}; | |
88 | |
89 \draw[tumgreen, fill=tumgreen!20] (3.7, 1) rectangle (5.8, -1); | |
90 \node[tumgreen] () at (4.75, -1.2) {$N_\beta$}; | |
91 | |
92 \node[state, initial] (i) at (0, 0) {}; | |
93 \node[state] (j) at (1.5, 0.5) {}; | |
94 \node[state] (k) at (1.5, -0.5) {}; | |
95 \node[state] (l) at (4, 0) {}; | |
96 \node[state, accepting] (m) at (5.5, 0) {}; | |
97 | |
98 \draw[->] (j) edge node {$\epsilon$} (l); | |
99 \draw[->] (k) edge node {$\epsilon$} (l); | |
100 \end{tikzpicture} | |
101 }\\ | |
102 \end{tabu} | |
103 \end{frame} | |
104 | |
105 \begin{frame} | |
106 \setbeamercovered{dynamic} | |
107 \frametitle{RE $\rightarrow$ $\epsilon$-NFA} | |
108 | |
109 \begin{tabu} to \linewidth {X} | |
110 \alert{$\gamma = \alpha \mid \beta$} \\ | |
111 \centering | |
112 \begin{tikzpicture}[automaton, small] | |
113 \draw[tumgreen, fill=tumgreen!20] (2, 1.5) rectangle (4.5, 0.5); | |
114 \node[tumgreen] () at (3.25, 0.3) {$N_\alpha$}; | |
115 | |
116 \draw[tumgreen, fill=tumgreen!20] (2, -0.5) rectangle (4.5, -1.5); | |
117 \node[tumgreen] () at (3.25, -1.7) {$N_\beta$}; | |
118 | |
119 \node[state, initial] (i) at (0, 0) {}; | |
120 | |
121 \node[state] (j) at (2.5, 1) {}; | |
122 \node[state, accepting] (k) at (4, 1) {}; | |
123 \node[state] (l) at (2.5, -1) {}; | |
124 \node[state, accepting] (m) at (4, -1) {}; | |
125 | |
126 \draw[->] (i) edge node {$\epsilon$} (j); | |
127 \draw[->] (i) edge node {$\epsilon$} (l); | |
128 \end{tikzpicture} \\ | |
129 \vfill | |
130 | |
131 \alert{$\gamma = \alpha^*$} \\ | |
132 \centering | |
133 \begin{tikzpicture}[automaton, small, bend angle=70] | |
134 \draw[tumgreen, fill=tumgreen!20] (2, 1) rectangle (4.5, -1); | |
135 \node[tumgreen] () at (3.25, -1.2) {$N_\alpha$}; | |
136 | |
137 \node[state, initial, accepting] (i) at (0, 0) {}; | |
138 | |
139 \node[state] (j) at (2.5, 0) {}; | |
140 \node[state, accepting] (k) at (4, 0.5) {}; | |
141 \node[state, accepting] (m) at (4, -0.5) {}; | |
142 | |
143 \draw[->] (i) edge node {$\epsilon$} (j); | |
144 \draw[->] (k) edge [bend right] node {$\epsilon$} (j); | |
145 \draw[->] (m) edge [bend left] node[above] {$\epsilon$} (j); | |
146 \end{tikzpicture} | |
147 \end{tabu} | |
148 \end{frame} | |
149 | |
150 \begin{frame} | |
151 \setbeamercovered{dynamic} | |
152 \frametitle{$\epsilon$-NFA $\rightarrow$ NFA} | |
153 | |
154 \begin{block}{Idee} | |
155 Entferne $\epsilon$-Kanten durch das Bilden von $\epsilon$-Hüllen. | |
156 \begin{enumerate} | |
157 \item<1-> Entferne \alert{unnötige Knoten}. | |
158 \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. | |
159 \item<1,4-> Entferne alle \alert{$\epsilon$-Kanten} und unerreichbare Knoten. | |
160 \item<1,5-> Wurde das leere Wort akzeptiert mache den \alert{Anfangszustand} zum Endzustand. | |
161 \end{enumerate} | |
162 \end{block} | |
163 | |
164 \vfill | |
165 | |
166 \begin{tikzpicture}[automaton, bend angle=40, node distance=2.1cm] | |
167 \useasboundingbox (-1.4,2) rectangle (9, -2); | |
168 | |
169 \node<-4>[state, initial] (q0) {$q_0$}; | |
170 \node[state] (q2) [right = 3.2cm of q0] {$q_2$}; | |
171 \node[state] (q3) [right of = q2] {$q_3$}; | |
172 \node[state, accepting] (q4) [right of = q3] {$q_4$}; | |
173 | |
174 \draw[->] (q2) edge node {$0$} (q3); | |
175 \draw[->] (q3) edge node {$1$} (q4); | |
176 | |
177 \draw<1-4>[->] (q3) edge [bend right] node [above] {$\epsilon$} (q2); | |
178 \draw[->] (q4) edge [bend right] node [above] {$1$} (q3); | |
179 \draw<1-4>[->] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); | |
180 | |
181 \node<1>[state] (q1) [right of = q0] {$q_1$}; | |
182 \draw<1>[->] (q0) edge node {$\epsilon$} (q1); | |
183 \draw<1>[->] (q1) edge node {$1$} (q2); | |
184 | |
185 \node<2>[state, fill=tumred!20] (q1) [right of = q0] {$q_1$}; | |
186 \draw<2>[->, tumred] (q0) edge node {$\epsilon$} (q1); | |
187 \draw<2>[->, tumred] (q1) edge node {$0$} (q2); | |
188 \draw<2->[->, tumblue] (q0) edge [bend left] node {$0$} (q2); | |
189 | |
190 \draw<3,4,5>[->, tumred] (q0) edge [bend right=20] node [below] {$\epsilon$} (q4); | |
191 \draw<3>[->, tumred] (q4) edge [bend right] node [above] {$1$} (q3); | |
192 \draw<3,4>[->, tumred] (q3) edge [bend right] node [above] {$\epsilon$} (q2); | |
193 \draw<3->[->, tumgreen] (q0) edge node {$1$} (q2); | |
194 | |
195 \draw<4->[->, tumgreen] (q2) edge [loop above] node [above] {$0$} (q2); | |
196 \draw<4->[->, tumgreen] (q3) edge [loop above] node [above] {$0$} (q3); | |
197 \draw<4->[->, tumgreen] (q0) edge [bend right=20] node [above] {$1$} (q3); | |
198 \draw<4->[->, tumgreen] (q4) edge [bend right=70] node [above] {$1$} (q2); | |
199 | |
200 \node<5>[state, initial, accepting, fill=tumgreen!20] (q0) {$q_0$}; | |
201 | |
202 \node<6->[state, initial, accepting] (q0) {$q_0$}; | |
203 \end{tikzpicture} | |
204 \end{frame} | |
205 | |
206 \begin{frame} | |
207 \setbeamercovered{dynamic} | |
208 \frametitle{NFA $\rightarrow$ DFA} | |
209 | |
210 \begin{block}{Idee (Potenzmengenkonstruktion)} | |
211 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)$}. | |
212 | |
213 \begin{itemize} | |
214 \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\ | |
215 \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\] | |
216 \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$ | |
217 \end{itemize} | |
218 \end{block} | |
219 | |
220 \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm] | |
221 \useasboundingbox (-1.4,2) rectangle (9, -2); | |
222 | |
223 \node[state, initial] (q0) {$q_0$}; | |
224 \node[state, accepting] (q1) [right of = q0] {$q_1$}; | |
225 | |
226 \draw[->] (q0) edge [loop above] node {$0,1$} (q0); | |
227 \draw[->] (q0) edge node {$1$} (q1); | |
228 | |
229 \node<2->(sep) [right of = q1] {$\rightarrow$}; | |
230 | |
231 \node<2->[state, initial, inner sep=1pt] (pq0) [right of = sep] {$q_{\{0\}}$}; | |
232 | |
233 \node<3->[state, accepting, inner sep=0pt] (pq01) [right of = pq0] {$q_{\{0,1\}}$}; | |
234 \draw<3->[->] (pq0) edge [loop above] node {$0$} (pq0); | |
235 \draw<3->[->] (pq0) edge [bend left] node {$1$} (pq01); | |
236 | |
237 \draw<4->[->] (pq01) edge [loop above] node {$1$} (pq01); | |
238 \draw<4->[->] (pq01) edge [bend left] node {$0$} (pq0); | |
239 | |
240 \end{tikzpicture} | |
241 \end{frame} | |
242 | |
243 \begin{frame} | |
244 \setbeamercovered{dynamic} | |
245 \frametitle{Produktautomat} | |
246 \begin{theorem} | |
247 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} | |
248 | |
249 \begin{align*} | |
250 M &:= (\alert{Q_1 \times Q_2}, \Sigma, \delta, (s_1, s_2), F_1 \times F_2) \\ | |
251 \delta\left( (q_1, q_2), a \right) &:= \left( \alert{\delta_1}(q_1, a), \alert{\delta_2}(q_2, a) \right) | |
252 \end{align*} | |
253 | |
254 ein DFA, der $L(M_1) \cap L(M_2)$ akzeptiert. | |
255 \end{theorem} | |
256 | |
257 \end{frame} | |
258 | |
259 \end{document} | 16 \end{document} |