309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
310 |
310 |
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
312 \mode<presentation>{ |
312 \mode<presentation>{ |
313 \begin{frame}[c] |
313 \begin{frame}[c] |
314 \frametitle{\begin{tabular}{c}The Derivative\end{tabular}} |
314 \frametitle{\begin{tabular}{c}The Derivative of a Rexp (2)\end{tabular}} |
315 |
315 |
316 \begin{center} |
316 \begin{center} |
317 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
317 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
318 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
318 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
319 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
319 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
320 \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then [] else $\varnothing$} & \\ |
320 \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then [] else $\varnothing$} & \\ |
321 \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ |
321 \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ |
322 \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{((der c r$_1$) $\cdot$ r$_2$) + } & \\ |
322 \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{if nullable r$_1$}\\ |
323 & & \bl{\hspace{3mm}(if nullable r$_1$ then der c r$_2$ else $\varnothing$)}\\ |
323 & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ |
|
324 & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\ |
324 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause |
325 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause |
325 |
326 |
326 \bl{ders [] r} & \bl{$\dn$} & \bl{r} & \\ |
327 \bl{ders [] r} & \bl{$\dn$} & \bl{r} & \\ |
327 \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\ |
328 \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\ |
328 \end{tabular} |
329 \end{tabular} |
428 already holds for \bl{s} |
429 already holds for \bl{s} |
429 \end{itemize} |
430 \end{itemize} |
430 \end{frame}} |
431 \end{frame}} |
431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
432 |
433 |
|
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
435 \mode<presentation>{ |
|
436 \begin{frame}[c] |
|
437 \frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}} |
|
438 |
|
439 Let \bl{Der c A} be the set defined as |
|
440 |
|
441 \begin{center} |
|
442 \bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } |
|
443 \end{center} |
|
444 |
|
445 Assume that \bl{$L$(der c r) = Der c ($L$(r))}. Prove that |
|
446 |
|
447 \begin{center} |
|
448 \bl{matcher(r, s) if and only if s $\in$ $L$(r)} |
|
449 \end{center} |
|
450 |
|
451 |
|
452 \end{frame}} |
|
453 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
433 |
454 |
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
455 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
435 \mode<presentation>{ |
456 \mode<presentation>{ |
436 \begin{frame}[c] |
457 \begin{frame}[c] |
437 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
458 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |