89 |
95 |
90 \normalsize |
96 \normalsize |
91 \begin{center} |
97 \begin{center} |
92 \begin{tabular}{ll} |
98 \begin{tabular}{ll} |
93 Email: & christian.urban at kcl.ac.uk\\ |
99 Email: & christian.urban at kcl.ac.uk\\ |
94 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
100 Office: & S1.27 (1st floor Strand Building)\\ |
95 Slides: & KEATS (also home work is there)\\ |
101 Slides: & KEATS (also home work is there)\\ |
96 \end{tabular} |
102 \end{tabular} |
97 \end{center} |
103 \end{center} |
98 |
104 |
99 |
105 |
100 \end{frame}} |
106 \end{frame}} |
101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
102 |
108 |
103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
104 \mode<presentation>{ |
110 \mode<presentation>{ |
105 \begin{frame}[t] |
111 \begin{frame}[c] |
106 \frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}} |
112 \frametitle{DFA Minimisation} |
107 |
|
108 A DFA \bl{$A(Q, q_0, F, \delta)$} consists of: |
|
109 |
|
110 \begin{itemize} |
|
111 \item a finite set of states \bl{$Q$} |
|
112 \item one of these states is the start state \bl{$q_0$} |
|
113 \item some states are accepting states \bl{$F$} |
|
114 \item a transition function \bl{$\delta$} |
|
115 \end{itemize}\pause |
|
116 |
|
117 \onslide<2->{ |
|
118 \begin{center} |
|
119 \begin{tabular}{l} |
|
120 \bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ |
|
121 \bl{$\hat{\delta}(q, c\!::\!s) = \hat{\delta}(\delta(q, c), s)$} |
|
122 \end{tabular} |
|
123 \end{center}} |
|
124 |
|
125 \only<3,4>{ |
|
126 \begin{center} |
|
127 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
128 \node[state, initial] (q02) at ( 0,1) {$q_{0}$}; |
|
129 \node[state] (q13) at ( 1,1) {$q_{1}$}; |
|
130 \node[state, accepting] (q4) at ( 2,1) {$q_2$}; |
|
131 \path[->] (q02) edge[bend left] node[above] {$a$} (q13) |
|
132 (q13) edge[bend left] node[below] {$b$} (q02) |
|
133 (q13) edge node[above] {$a$} (q4) |
|
134 (q02) edge [loop below] node {$b$} () |
|
135 (q4) edge [loop right] node {$a, b$} () |
|
136 ; |
|
137 \end{tikzpicture} |
|
138 \end{center}}% |
|
139 % |
|
140 \only<5>{ |
|
141 \begin{center} |
|
142 \bl{$L(A) \dn \{ s \;|\; \hat{\delta}(q_0, s) \in F\}$} |
|
143 \end{center}} |
|
144 |
|
145 \end{frame}} |
|
146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
147 |
|
148 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
149 \mode<presentation>{ |
|
150 \begin{frame}[t] |
|
151 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
|
152 |
|
153 An NFA \bl{$A(Q, q_0, F, \delta)$} consists again of: |
|
154 |
|
155 \begin{itemize} |
|
156 \item a finite set of states |
|
157 \item one of these states is the start state |
|
158 \item some states are accepting states |
|
159 \item a transition \alert{relation}\medskip |
|
160 \end{itemize} |
|
161 |
|
162 |
|
163 \begin{center} |
|
164 \begin{tabular}{c} |
|
165 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\ |
|
166 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\ |
|
167 \end{tabular} |
|
168 \hspace{10mm} |
|
169 \begin{tabular}{c} |
|
170 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\ |
|
171 \end{tabular} |
|
172 \end{center}\pause\medskip |
|
173 |
|
174 A string \bl{s} is accepted by an NFA, if there is a ``lucky'' sequence to an accepting state. |
|
175 |
|
176 \end{frame}} |
|
177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
178 |
|
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
180 \mode<presentation>{ |
|
181 \begin{frame}[c] |
|
182 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
183 |
|
184 Last week I showed you\bigskip |
|
185 |
|
186 \begin{itemize} |
|
187 \item an algorithm for automata minimisation |
|
188 |
|
189 \item an algorithm for transforming a regular expression into an NFA |
|
190 |
|
191 \item an algorithm for transforming an NFA into a DFA (subset construction) |
|
192 |
|
193 \end{itemize} |
|
194 |
|
195 \end{frame}} |
|
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
197 |
|
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
199 \mode<presentation>{ |
|
200 \begin{frame}[c] |
|
201 \frametitle{\begin{tabular}{c}This Week\end{tabular}} |
|
202 |
|
203 Go over the algorithms again, but with two new things and \ldots\medskip |
|
204 |
|
205 \begin{itemize} |
|
206 \item with the example: what is the regular expression that accepts every string, except those ending |
|
207 in \bl{aa}?\medskip |
|
208 |
|
209 \item Go over the proof for \bl{$L(rev(r)) = Rev(L(r))$}.\medskip |
|
210 |
|
211 \item Anything else so far. |
|
212 \end{itemize} |
|
213 |
|
214 \end{frame}} |
|
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
216 |
|
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
218 \mode<presentation>{ |
|
219 \begin{frame}[c] |
|
220 \frametitle{\begin{tabular}{c}Proofs By Induction\end{tabular}} |
|
221 |
|
222 \begin{itemize} |
|
223 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
|
224 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already |
|
225 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip |
|
226 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already |
|
227 holds for \bl{r$_1$} and \bl{r$_2$}. |
|
228 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
|
229 holds for \bl{r}. |
|
230 \end{itemize} |
|
231 |
|
232 \begin{center} |
|
233 \bl{$P(r):\;\;L(rev(r)) = Rev(L(r))$} |
|
234 \end{center} |
|
235 |
|
236 \end{frame}} |
|
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
238 |
|
239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
240 \mode<presentation>{ |
|
241 \begin{frame}[t] |
|
242 |
|
243 What is the regular expression that accepts every string, except those ending |
|
244 in \bl{aa}?\pause\bigskip |
|
245 |
|
246 \begin{center} |
|
247 \begin{tabular}{l} |
|
248 \bl{(a + b)$^*$ba}\\ |
|
249 \bl{(a + b)$^*$ab}\\ |
|
250 \bl{(a + b)$^*$bb}\\\pause |
|
251 \bl{a}\\ |
|
252 \bl{\texttt{""}} |
|
253 \end{tabular} |
|
254 \end{center}\pause |
|
255 |
|
256 What are the strings to be avoided?\pause\medskip |
|
257 |
|
258 \begin{center} |
|
259 \bl{(a + b)$^*$aa} |
|
260 \end{center} |
|
261 |
|
262 \end{frame}} |
|
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
264 |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 \mode<presentation>{ |
|
267 \begin{frame}[t] |
|
268 |
|
269 An NFA for \bl{(a + b)$^*$aa} |
|
270 |
|
271 \begin{center} |
|
272 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
273 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
274 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
275 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
276 \path[->] (q0) edge node[above] {$a$} (q1) |
|
277 (q1) edge node[above] {$a$} (q2) |
|
278 (q0) edge [loop below] node {$a$} () |
|
279 (q0) edge [loop above] node {$b$} () |
|
280 ; |
|
281 \end{tikzpicture} |
|
282 \end{center}\pause |
|
283 |
|
284 Minimisation for DFAs\\ |
|
285 Subset Construction for NFAs |
|
286 |
|
287 \end{frame}} |
|
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
289 |
|
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
291 \mode<presentation>{ |
|
292 \begin{frame}[c] |
|
293 \frametitle{\begin{tabular}{c}DFA Minimisation\end{tabular}} |
|
294 |
|
295 |
113 |
296 \begin{enumerate} |
114 \begin{enumerate} |
297 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
115 \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} |
298 \item Mark all pairs that accepting and non-accepting states |
116 \item Mark all pairs that accepting and non-accepting states |
299 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
117 \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} tests wether |
300 \begin{center} |
118 \begin{center} |
301 \bl{($\delta$(q,c), $\delta$(p,c))} |
119 \bl{$(\delta(q, c), \delta(p,c))$} |
302 \end{center} |
120 \end{center} |
303 are marked. If yes, then also mark \bl{(q, p)}. |
121 are marked. If yes, then also mark \bl{$(q, p)$}. |
304 \item Repeat last step until nothing changed. |
122 \item Repeat last step until no chance. |
305 \item All unmarked pairs can be merged. |
123 \item All unmarked pairs can be merged. |
306 \end{enumerate} |
124 \end{enumerate} |
307 |
125 |
308 \end{frame}} |
126 \end{frame}} |
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
127 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
310 |
128 |
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
129 |
312 \mode<presentation>{ |
130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
313 \begin{frame}[c] |
131 \mode<presentation>{ |
314 |
132 \begin{frame}<1-2>[c] |
315 Minimal DFA \only<1>{\bl{(a + b)$^*$aa}}\only<2->{\alert{not} \bl{(a + b)$^*$aa}} |
133 |
316 |
134 \begin{center} |
317 \begin{center} |
135 \begin{tikzpicture}[>=stealth',very thick,auto, |
318 \begin{tikzpicture}[scale=2, line width=0.5mm] |
136 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
319 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
137 \node[state,initial] (q_0) {$q_0$}; |
320 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
138 \node[state] (q_1) [right=of q_0] {$q_1$}; |
321 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
139 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
322 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
140 \node[state] (q_3) [right=of q_2] {$q_3$}; |
323 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
141 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
324 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
142 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
325 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
143 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
326 (q1) edge[bend left] node[above] {$b$} (q0) |
144 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
327 (q2) edge[bend left=50] node[below] {$b$} (q0) |
145 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
328 (q1) edge node[above] {$a$} (q2) |
146 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
329 (q2) edge [loop right] node {$a$} () |
147 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
330 (q0) edge [loop below] node {$b$} () |
148 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
331 ; |
149 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
150 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
332 \end{tikzpicture} |
151 \end{tikzpicture} |
333 \end{center} |
152 \end{center} |
334 |
153 |
335 \onslide<3>{How to get from a DFA to a regular expression?} |
154 \mbox{}\\[-20mm]\mbox{} |
336 |
155 |
337 \end{frame}} |
156 \begin{center} |
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 \begin{tikzpicture}[scale=0.8,line width=0.8mm] |
339 |
158 \draw (0,0) -- (4,0); |
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
159 \draw (0,1) -- (4,1); |
341 \mode<presentation>{ |
160 \draw (0,2) -- (3,2); |
342 \begin{frame}[c] |
161 \draw (0,3) -- (2,3); |
343 |
162 \draw (0,4) -- (1,4); |
344 \begin{center} |
163 |
345 \begin{tikzpicture}[scale=2, line width=0.5mm] |
164 \draw (0,0) -- (0, 4); |
346 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
165 \draw (1,0) -- (1, 4); |
347 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
166 \draw (2,0) -- (2, 3); |
348 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
167 \draw (3,0) -- (3, 2); |
349 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
168 \draw (4,0) -- (4, 1); |
350 (q1) edge[bend left] node[above] {$b$} (q0) |
169 |
351 (q2) edge[bend left=50] node[below] {$b$} (q0) |
170 \draw (0.5,-0.5) node {$q_0$}; |
352 (q1) edge node[above] {$a$} (q2) |
171 \draw (1.5,-0.5) node {$q_1$}; |
353 (q2) edge [loop right] node {$a$} () |
172 \draw (2.5,-0.5) node {$q_2$}; |
354 (q0) edge [loop below] node {$b$} () |
173 \draw (3.5,-0.5) node {$q_3$}; |
355 ; |
174 |
|
175 \draw (-0.5, 3.5) node {$q_1$}; |
|
176 \draw (-0.5, 2.5) node {$q_2$}; |
|
177 \draw (-0.5, 1.5) node {$q_3$}; |
|
178 \draw (-0.5, 0.5) node {$q_4$}; |
|
179 |
|
180 \draw (0.5,0.5) node {\large$\star$}; |
|
181 \draw (1.5,0.5) node {\large$\star$}; |
|
182 \draw (2.5,0.5) node {\large$\star$}; |
|
183 \draw (3.5,0.5) node {\large$\star$}; |
|
184 \end{tikzpicture}\\ |
|
185 \end{center} |
|
186 |
|
187 \end{frame}} |
|
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
189 |
|
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
191 \mode<presentation>{ |
|
192 \begin{frame}<1-2>[c] |
|
193 |
|
194 \begin{center} |
|
195 \begin{tabular}{@{\hspace{-8mm}}cc@{}} |
|
196 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
197 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
198 \node[state,initial] (q_0) {$q_0$}; |
|
199 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
200 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
201 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
202 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
203 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
204 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
205 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
206 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
207 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
208 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
209 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
210 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
211 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
356 \end{tikzpicture} |
212 \end{tikzpicture} |
357 \end{center}\pause\bigskip |
213 & |
358 |
214 \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] |
359 \onslide<2->{ |
215 \draw (0,0) -- (4,0); |
360 \begin{center} |
216 \draw (0,1) -- (4,1); |
361 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
217 \draw (0,2) -- (3,2); |
362 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
218 \draw (0,3) -- (2,3); |
363 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
219 \draw (0,4) -- (1,4); |
364 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
220 |
365 |
221 \draw (0,0) -- (0, 4); |
|
222 \draw (1,0) -- (1, 4); |
|
223 \draw (2,0) -- (2, 3); |
|
224 \draw (3,0) -- (3, 2); |
|
225 \draw (4,0) -- (4, 1); |
|
226 |
|
227 \draw (0.5,-0.5) node {$q_0$}; |
|
228 \draw (1.5,-0.5) node {$q_1$}; |
|
229 \draw (2.5,-0.5) node {$q_2$}; |
|
230 \draw (3.5,-0.5) node {$q_3$}; |
|
231 |
|
232 \draw (-0.5, 3.5) node {$q_1$}; |
|
233 \draw (-0.5, 2.5) node {$q_2$}; |
|
234 \draw (-0.5, 1.5) node {$q_3$}; |
|
235 \draw (-0.5, 0.5) node {$q_4$}; |
|
236 |
|
237 \draw (0.5,0.5) node {\large$\star$}; |
|
238 \draw (1.5,0.5) node {\large$\star$}; |
|
239 \draw (2.5,0.5) node {\large$\star$}; |
|
240 \draw (3.5,0.5) node {\large$\star$}; |
|
241 \draw (0.5,1.5) node {\large$\star$}; |
|
242 \draw (2.5,1.5) node {\large$\star$}; |
|
243 \draw (0.5,3.5) node {\large$\star$}; |
|
244 \draw (1.5,2.5) node {\large$\star$}; |
|
245 \end{tikzpicture}} |
366 \end{tabular} |
246 \end{tabular} |
367 \end{center} |
247 \end{center} |
368 } |
248 |
369 |
249 |
370 \end{frame}} |
250 \mbox{}\\[-20mm]\mbox{} |
371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
251 |
372 |
252 \begin{center} |
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
253 \begin{tikzpicture}[>=stealth',very thick,auto, |
374 \mode<presentation>{ |
254 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
375 \begin{frame}[c] |
255 \node[state,initial] (q_02) {$q_{0, 2}$}; |
376 |
256 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; |
377 \begin{center} |
257 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; |
378 \begin{tikzpicture}[scale=2, line width=0.5mm] |
258 \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); |
379 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
259 \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); |
380 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
260 \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); |
381 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
261 \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); |
382 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
262 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
383 (q1) edge[bend left] node[above] {$b$} (q0) |
263 \end{tikzpicture}\\ |
384 (q2) edge[bend left=50] node[below] {$b$} (q0) |
264 minimal automaton |
385 (q1) edge node[above] {$a$} (q2) |
265 \end{center} |
386 (q2) edge [loop right] node {$a$} () |
266 |
387 (q0) edge [loop below] node {$b$} () |
267 \end{frame}} |
388 ; |
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
269 |
|
270 |
|
271 |
|
272 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
273 \mode<presentation>{ |
|
274 \begin{frame}[c] |
|
275 |
|
276 \begin{center} |
|
277 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
278 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
279 \only<1>{\node[state,initial] (q_0) {$q_0$};} |
|
280 \only<2->{\node[state,accepting] (q_0) {$q_0$};} |
|
281 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
282 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
283 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
284 \only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};} |
|
285 \only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};} |
|
286 \only<1-2>{ |
|
287 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
288 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
289 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
290 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
291 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
292 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
293 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
294 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
295 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
|
296 \only<3->{ |
|
297 \path[<-] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
298 \path[<-] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
299 \path[<-] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
300 \path[<-] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
301 \path[<-] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
302 \path[<-] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
303 \path[<-] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
304 \path[<-] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
305 \path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
389 \end{tikzpicture} |
306 \end{tikzpicture} |
390 \end{center}\bigskip |
307 \end{center} |
391 |
|
392 \onslide<2->{ |
|
393 \begin{center} |
|
394 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
395 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
396 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
397 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
398 |
|
399 \end{tabular} |
|
400 \end{center} |
|
401 } |
|
402 |
|
403 \onslide<3->{ |
|
404 Arden's Lemma: |
|
405 \begin{center} |
|
406 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
407 \end{center} |
|
408 } |
|
409 |
|
410 \end{frame}} |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 |
|
413 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
414 \mode<presentation>{ |
|
415 \begin{frame}[c] |
|
416 \frametitle{\begin{tabular}{c}Algorithms on Automata\end{tabular}} |
|
417 |
|
418 |
308 |
419 \begin{itemize} |
309 \begin{itemize} |
420 \item Reg $\rightarrow$ NFA: Thompson-McNaughton-Yamada method\medskip |
310 \item<2-> exchange initial / accepting states |
421 \item NFA $\rightarrow$ DFA: Subset Construction\medskip |
311 \item<3-> reverse all edges |
422 \item DFA $\rightarrow$ Reg: Brzozowski's Algebraic Method\medskip |
312 \item<4-> subset construction $\Rightarrow$ DFA |
423 \item DFA minimisation: Hopcrofts Algorithm\medskip |
313 \item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA} |
424 \item complement DFA |
314 |
425 \end{itemize} |
315 \end{itemize} |
426 |
316 |
427 \end{frame}} |
317 \end{frame}} |
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
319 |
|
320 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
321 \mode<presentation>{ |
|
322 \begin{frame}[c] |
|
323 |
|
324 \texttt{\consolas\lstinputlisting{../progs/fib.while}} |
|
325 |
|
326 \end{frame}} |
|
327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
328 |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 \mode<presentation>{ |
|
331 \begin{frame}[c] |
|
332 |
|
333 \texttt{\consolas\lstinputlisting{../progs/collatz.while}} |
|
334 |
|
335 \end{frame}} |
|
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
337 |
|
338 |
|
339 |
|
340 |
429 \newcommand{\qq}{\mbox{\texttt{"}}} |
341 \newcommand{\qq}{\mbox{\texttt{"}}} |
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
431 \mode<presentation>{ |
343 \mode<presentation>{ |
432 \begin{frame}[c] |
344 \begin{frame}[c] |
433 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
345 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |