2 \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} |
2 \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} |
3 \usepackage{../slides} |
3 \usepackage{../slides} |
4 \usepackage{../graphics} |
4 \usepackage{../graphics} |
5 \usepackage{../langs} |
5 \usepackage{../langs} |
6 \usepackage{../data} |
6 \usepackage{../data} |
|
7 |
|
8 \usepackage{tcolorbox} |
|
9 \newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black} |
|
10 \newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1} |
|
11 \newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1} |
|
12 |
|
13 |
7 |
14 |
8 \hfuzz=220pt |
15 \hfuzz=220pt |
9 |
16 |
10 \lstset{language=Scala, |
17 \lstset{language=Scala, |
11 style=mystyle, |
18 style=mystyle, |
242 \end{center} |
249 \end{center} |
243 |
250 |
244 \end{frame} |
251 \end{frame} |
245 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
246 |
253 |
|
254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
255 \begin{frame}[c] |
|
256 \frametitle{Simplification Example} |
|
257 |
|
258 %%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows |
|
259 |
|
260 \begin{center} |
|
261 \def\arraystretch{2} |
|
262 \begin{tabular}{@{}lcl} |
|
263 \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
|
264 & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\ |
|
265 & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\ |
|
266 & \bl{$=$} & \bl{$b \cdot r$}\\ |
|
267 \end{tabular} |
|
268 \end{center} |
|
269 |
|
270 \end{frame} |
|
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
272 |
|
273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
274 \begin{frame}[c] |
|
275 \frametitle{Simplification Example} |
|
276 |
|
277 %%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows |
|
278 |
|
279 \begin{center} |
|
280 \def\arraystretch{2} |
|
281 \begin{tabular}{@{}lcl} |
|
282 \bl{$((\ZERO \cdot b) + \ZERO) \cdot r$} |
|
283 & \bl{$\Rightarrow$} & \bl{$((\underline{\ZERO \cdot b}) + \ZERO) \cdot r$}\\ |
|
284 & \bl{$=$} & \bl{$(\underline{\ZERO + \ZERO}) \cdot r$}\\ |
|
285 & \bl{$=$} & \bl{$\ZERO \cdot r$}\\ |
|
286 & \bl{$=$} & \bl{$\ZERO$}\\ |
|
287 \end{tabular} |
|
288 \end{center} |
|
289 |
|
290 \end{frame} |
|
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
247 |
292 |
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
249 \begin{frame}[t] |
294 \begin{frame}[t] |
250 \frametitle{Semantic Derivative\\[5mm]} |
295 \frametitle{Semantic Derivative\\[5mm]} |
251 |
296 |
375 \end{frame} |
420 \end{frame} |
376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
421 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
377 |
422 |
378 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
379 \begin{frame}[c] |
424 \begin{frame}[c] |
|
425 \frametitle{Derivative Example} |
|
426 |
|
427 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
|
428 |
|
429 \begin{center} |
|
430 \def\arraystretch{1.5} |
|
431 \begin{tabular}{@{}lcl} |
|
432 \bl{$\der\,a\,((a \cdot b) + b)^*$} |
|
433 & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\ |
|
434 & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\ |
|
435 & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\ |
|
436 & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\ |
|
437 & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\ |
|
438 & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
|
439 \end{tabular} |
|
440 \end{center} |
|
441 |
|
442 \end{frame} |
|
443 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
444 |
|
445 |
|
446 |
|
447 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
448 \begin{frame}[c] |
380 \frametitle{\mbox{The Brzozowski Algorithm}} |
449 \frametitle{\mbox{The Brzozowski Algorithm}} |
381 |
450 |
382 \begin{center} |
451 %\begin{center} |
383 \begin{tabular}{l} |
452 %\begin{tabular}{l} |
384 \bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$} |
453 %\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$} |
385 \end{tabular} |
454 %\end{tabular} |
386 \end{center} |
455 %\end{center} |
387 |
456 |
|
457 \begin{center} |
|
458 \begin{mybox3}{} |
|
459 \bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$} |
|
460 \end{mybox3} |
|
461 \end{center} |
388 |
462 |
389 \end{frame} |
463 \end{frame} |
390 %%%%%%%%%%%%%%%%% |
464 %%%%%%%%%%%%%%%%% |
391 |
465 |
392 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
428 \end{enumerate} |
502 \end{enumerate} |
429 |
503 |
430 The matching algorithm works similarly, just over regular expressions instead of sets. |
504 The matching algorithm works similarly, just over regular expressions instead of sets. |
431 \end{frame} |
505 \end{frame} |
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
507 |
|
508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
509 \begin{frame}[c] |
|
510 \frametitle{The Idea with Derivatives} |
|
511 |
|
512 Input: string \bl{$abc$} and regular expression \bl{$r$}\medskip |
|
513 |
|
514 \begin{enumerate} |
|
515 \item \bl{$der\,a\,r$} |
|
516 \item \bl{$der\,b\,(der\,a\,r)$} |
|
517 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
|
518 \item finally check whether the last regular expression can match the empty string |
|
519 \end{enumerate} |
|
520 |
|
521 \end{frame} |
|
522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
433 |
523 |
434 |
524 |
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
525 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
436 \begin{frame}[c] |
526 \begin{frame}[c] |
437 \frametitle{Oops\ldots \boldmath\;$a^{?\{n\}} \cdot a^{\{n\}}$} |
527 \frametitle{Oops\ldots \boldmath\;$a^{?\{n\}} \cdot a^{\{n\}}$} |
774 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
864 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
775 |
865 |
776 |
866 |
777 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
867 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
778 \begin{frame}[c] |
868 \begin{frame}[c] |
779 \frametitle{Coursework} |
869 \frametitle{Coursework 1} |
780 |
870 |
781 \underline{Strand 1:} |
871 %%\underline{Strand 1:} |
782 |
872 |
783 \begin{itemize} |
873 \begin{itemize} |
784 \item Submission on Friday 11 October\\accepted until Monday 14 @ 18:00\medskip |
874 \item Submission on Friday 16 October @ 18:00\medskip |
785 \item source code needs to be submitted as well\medskip |
875 \item source code needs to be submitted as well\medskip |
786 \item you can re-use my Scala code from KEATS \\ |
876 \item you can re-use my Scala code from KEATS \\ |
787 or use any programming language you like\medskip |
877 and use any programming language you like\medskip |
788 \item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize |
878 \item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize |
789 \end{itemize} |
879 \end{itemize} |
790 |
880 |
791 \end{frame} |
881 \end{frame} |
792 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
882 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
793 |
883 |
794 |
884 |
795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
885 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
796 \begin{frame}[t] |
886 \begin{frame}[t] |
797 \frametitle{Proofs about Rexps} |
887 \frametitle{Proofs about Rexps} |
798 |
888 |
799 Remember their inductive definition:\\[5cm] |
889 Remember their inductive definition:\\[5cm] |
800 |
890 |
1060 Last week I showed you a regular expression matcher |
1150 Last week I showed you a regular expression matcher |
1061 that works provably correct in all cases (we only |
1151 that works provably correct in all cases (we only |
1062 started with the proving part though) |
1152 started with the proving part though) |
1063 |
1153 |
1064 \begin{center} |
1154 \begin{center} |
1065 \bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
1155 \bl{$matcher\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$} |
1066 \end{center}\bigskip\bigskip |
1156 \end{center}\bigskip\bigskip |
1067 |
1157 |
1068 \small |
1158 \small |
1069 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
1159 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} |
1070 |
1160 |
1071 \end{frame} |
1161 \end{frame} |
1072 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1073 |
1163 |
1074 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1164 |
1075 \begin{frame}[c] |
1165 |
1076 \frametitle{The Derivative of a Rexp} |
1166 |
1077 |
1167 |
1078 \begin{center} |
1168 |
1079 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
1080 \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
|
1081 \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
|
1082 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
|
1083 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
|
1084 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
|
1085 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
|
1086 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
|
1087 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\ |
|
1088 |
|
1089 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
|
1090 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
|
1091 \end{tabular} |
|
1092 \end{center} |
|
1093 |
|
1094 \end{frame} |
|
1095 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1096 |
|
1097 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1098 \begin{frame}[c] |
|
1099 \frametitle{Example} |
|
1100 |
|
1101 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
|
1102 |
|
1103 \begin{center} |
|
1104 \def\arraystretch{1.5} |
|
1105 \begin{tabular}{@{}lcl} |
|
1106 \bl{$\der\,a\,((a \cdot b) + b)^*$} |
|
1107 & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\ |
|
1108 & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\ |
|
1109 & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\ |
|
1110 & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\ |
|
1111 & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\ |
|
1112 & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\ |
|
1113 \end{tabular} |
|
1114 \end{center} |
|
1115 |
|
1116 \end{frame} |
|
1117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1118 |
|
1119 |
|
1120 |
|
1121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1122 \begin{frame}[c] |
|
1123 |
|
1124 Input: string \bl{$abc$} and regular expression \bl{$r$} |
|
1125 |
|
1126 \begin{enumerate} |
|
1127 \item \bl{$der\,a\,r$} |
|
1128 \item \bl{$der\,b\,(der\,a\,r)$} |
|
1129 \item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause |
|
1130 \item finally check whether the last regular expression can match the empty string |
|
1131 \end{enumerate} |
|
1132 |
|
1133 \end{frame} |
|
1134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1135 |
|
1136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1137 \begin{frame}[t] |
|
1138 \frametitle{Simplification} |
|
1139 |
|
1140 Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows |
|
1141 |
|
1142 \begin{center} |
|
1143 \def\arraystretch{2} |
|
1144 \begin{tabular}{@{}lcl} |
|
1145 \bl{$((\ONE \cdot b) + \ZERO) \cdot r$} |
|
1146 & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\ |
|
1147 & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\ |
|
1148 & \bl{$=$} & \bl{$b \cdot r$}\\ |
|
1149 \end{tabular} |
|
1150 \end{center} |
|
1151 |
|
1152 \end{frame} |
|
1153 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1154 |
1169 |
1155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1170 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1156 \begin{frame}[c] |
1171 \begin{frame}[c] |
1157 \frametitle{Proofs about Rexp} |
1172 \frametitle{Proofs about Rexp} |
1158 |
1173 |