# HG changeset patch # User Christian Urban # Date 1569842835 -3600 # Node ID 0367aa7c764b628af34223c6bc4523c16651979c # Parent 27f71d2755f0d64426fbdb8b5fa1972efd98fe0f updated diff -r 27f71d2755f0 -r 0367aa7c764b progs/bfc0.scala --- a/progs/bfc0.scala Thu Sep 26 14:19:23 2019 +0100 +++ b/progs/bfc0.scala Mon Sep 30 12:27:15 2019 +0100 @@ -52,7 +52,7 @@ def compile_run(prog: String) = { compile("tmp", prog) - "gcc -O0 -o tmp tmp.c".! + "gcc -O3 -o tmp tmp.c".! "./tmp".! () } diff -r 27f71d2755f0 -r 0367aa7c764b progs/pow.scala --- a/progs/pow.scala Thu Sep 26 14:19:23 2019 +0100 +++ b/progs/pow.scala Mon Sep 30 12:27:15 2019 +0100 @@ -12,7 +12,7 @@ val B = Set("a", "b", "c", "") pow(B, 4) pow(B, 4).size // -> 121 - +pow(B, 3).size val B2 = Set("a", "b", "c", "") diff -r 27f71d2755f0 -r 0367aa7c764b progs/re3.scala --- a/progs/re3.scala Thu Sep 26 14:19:23 2019 +0100 +++ b/progs/re3.scala Mon Sep 30 12:27:15 2019 +0100 @@ -88,13 +88,13 @@ //test: (a?{n}) (a{n}) -for (i <- 0 to 7000 by 1000) { - println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") +for (i <- 0 to 8000 by 1000) { + println(f"$i: ${time_needed(3, matcher(EVIL1(i), "a" * i))}%.5f") } //test: (a*)* b for (i <- 0 to 6000000 by 500000) { - println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") + println(f"$i: ${time_needed(3, matcher(EVIL2, "a" * i))}%.5f") } diff -r 27f71d2755f0 -r 0367aa7c764b progs/re4.scala --- a/progs/re4.scala Thu Sep 26 14:19:23 2019 +0100 +++ b/progs/re4.scala Mon Sep 30 12:27:15 2019 +0100 @@ -95,7 +95,7 @@ // test: (a?{n}) (a{n}) -for (i <- 0 to 7000000 by 500000) { +for (i <- 0 to 11000 by 1000) { println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") } diff -r 27f71d2755f0 -r 0367aa7c764b slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 27f71d2755f0 -r 0367aa7c764b slides/slides02.tex --- a/slides/slides02.tex Thu Sep 26 14:19:23 2019 +0100 +++ b/slides/slides02.tex Mon Sep 30 12:27:15 2019 +0100 @@ -1,3 +1,4 @@ +% !TEX program = xelatex \documentclass[dvipsnames,14pt,t]{beamer} \usepackage{../slides} \usepackage{../graphics} @@ -34,9 +35,10 @@ \normalsize \begin{center} \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - Office: & N7.07 (North Wing, Bush House)\\ - Slides: & KEATS (also homework is there) + Email: & christian.urban at kcl.ac.uk\\ + Office Hours: & Thursdays 12 -- 14\\ + Location: & N7.07 (North Wing, Bush House)\\ + Slides \& Progs: & KEATS (also homework is there)\\ \end{tabular} \end{center} @@ -100,51 +102,73 @@ \end{center} \small -In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8. +In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8, +JavaScript and Python. \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Evil Regular Expressions} - -\begin{itemize} -\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip -\item Evil regular expressions\medskip -\begin{itemize} -\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} -\item \bl{$(a^*)^*$} -\item \bl{$([a$\,-\,$z]^+)^*$} -\item \bl{$(a + a \cdot a)^*$} -\item \bl{$(a + a^?)^*$} -\end{itemize} - -\item sometimes also called \alert{catastrophic backtracking}\bigskip -\item \small\ldots I hope you have watched the video by the - StackExchange engineer -\end{itemize} - -\end{frame} +%\begin{frame}[c] +%\frametitle{Evil Regular Expressions} +% +%\begin{itemize} +%\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip +%\item Evil regular expressions\medskip +%\begin{itemize} +%\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} +%\item \bl{$(a^*)^*$} +%\item \bl{$([a$\,-\,$z]^+)^*$} +%\item \bl{$(a + a \cdot a)^*$} +%\item \bl{$(a + a^?)^*$} +%\end{itemize} +% +%\item sometimes also called \alert{catastrophic backtracking}\bigskip +%\item \small\ldots I hope you have watched the video by the +% StackExchange engineer +%\end{itemize} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Languages} +\frametitle{(Basic) Regular Expressions} + +Their inductive definition: + +\begin{center} + \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ + & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ + & \bl{$\mid$} & \bl{$c$} & character\\ + & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ + & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ + & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ + \end{tabular} +\end{center} +\vspace{\fill} + +Q: \;What about \;\bl{$r \cdot 0$} \; ? +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Languages (Sets of Strings)} \begin{itemize} \item A \alert{\bf Language} is a set of strings, for example\medskip \begin{center} -\bl{$\{[], hello, \textit{foobar}, a, abc\}$} +\bl{$\{[], hello, foobar, a, abc\}$} \end{center}\bigskip -\item \alert{\bf Concatenation} of strings and languages +\item \alert{\bf Concatenation} for strings and languages \begin{center} \begin{tabular}{rcl} -\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ -\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} +\bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ +\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} \end{tabular} \end{center} \bigskip @@ -157,9 +181,53 @@ \] \end{itemize} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Two Corner Cases} + + \Large + \begin{center} + \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ + \bl{$A \,@\, \{\} = \;?$} + \end{center} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{ + The Meaning of a\\[-2mm] + Regular Expression} + + ...all the strings a regular expression can match. + +\begin{center} + \begin{tabular}{rcl} + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ + \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \\ + \end{tabular} +\end{center} + +\begin{textblock}{14}(1.5,13.5)\small +\bl{$L$} is a function from regular expressions to +sets of strings (languages):\smallskip\\ +\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +\end{textblock} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -192,26 +260,23 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Homework Question} - -\begin{itemize} -\item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip - -\begin{center} -How many strings are in \bl{$A^4$}? -\end{center}\bigskip\medskip\pause - - -\begin{center} -\begin{tabular}{l} -What if \bl{$A = \{[a],[b],[c],[]\}$};\\ -how many strings are then in \bl{$A^4$}? -\end{tabular} -\end{center} -\end{itemize} - + \frametitle{Homework Question} + + \begin{itemize} + \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip + + \item[] + How many strings are in \bl{$A^4$}\,? + \bigskip\medskip\pause + + + \item[] + What if \bl{$A = \{[a],[b],[c],[]\}$};\\ + how many strings are then in \bl{$A^4$}\,? + \end{itemize} + \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -252,26 +317,124 @@ The Meaning of a\\[-2mm] Regular Expression} -\begin{textblock}{15}(1,4) +...all the strings a regular expression can match. + +\begin{center} \begin{tabular}{rcl} \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ - \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ \end{tabular} -\end{textblock} +\end{center} -\begin{textblock}{9}(6,12)\small -\bl{$L$} is a function from regular expressions to -sets of strings (languages):\smallskip\\ -\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} -\end{textblock} +%\begin{textblock}{9}(6,12)\small +%\bl{$L$} is a function from regular expressions to +%sets of strings (languages):\smallskip\\ +%\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +%\end{textblock} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{ + When Are Two Regular\\[-1mm] + Expressions Equivalent?} + + \begin{bubble}[10cm] + \large + Two regular expressions \bl{$r_1$} and \bl{$r_2$} are equivalent + provided:\medskip + \begin{center} + \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} + \end{center}\medskip + \end{bubble} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some Concrete Equivalences} + +\begin{center} +\bl{\begin{tabular}{rcl} +$(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ +$a + a$ & $\equiv$ & $a$\\ +$a + b$ & $\equiv$ & $b + a$\\ +$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\ +$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause +$a \cdot a$ & $\not\equiv$ & $a$\\ +$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\ +\end{tabular}} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some Corner Cases} + +\begin{center} +\bl{\begin{tabular}{rcl} +$a \cdot \ZERO$ & $\not\equiv$ & $a$\\ +$a + \ONE$ & $\not\equiv$ & $a$\\ +$\ONE$ & $\equiv$ & $\ZERO^*$\\ +$\ONE^*$ & $\equiv$ & $\ONE$\\ +$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\ +\end{tabular}} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some Simplification Rules} + +\begin{center} +\bl{\begin{tabular}{rcl} +$r + \ZERO$ & $\equiv$ & $r$\\ +$\ZERO + r$ & $\equiv$ & $r$\\ +$r \cdot \ONE$ & $\equiv$ & $r$\\ +$\ONE \cdot r$ & $\equiv$ & $r$\\ +$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\ +$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\ +$r + r$ & $\equiv$ & $r$ +\end{tabular}} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Specification for Matching} + +\begin{bubble}[10cm] +\large +A regular expression \bl{$r$} matches a string~\bl{$s$} +provided: +\begin{center} +\bl{$s \in L(r)$} +\end{center}\medskip +\end{bubble} + +\bigskip\bigskip + +\ldots and the point of the this lecture is to decide this problem as +fast as possible (unlike Python, Ruby, Java etc) + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}} @@ -289,8 +452,6 @@ \begin{frame}[t] \frametitle{Semantic Derivative\\[5mm]} - - \begin{itemize} \item The \alert{\bf Semantic Derivative} of a \underline{language}\\ w.r.t.~to a character \bl{$c$}: @@ -308,7 +469,7 @@ $\Der\,b\,A$ & $=$ & $\{\mathit{ar}\}$\\ $\Der\,a\,A$ & $=$ & $\{\}$\pause \end{tabular}} -\end{center} +\end{center}\medskip We can extend this definition to strings @@ -324,143 +485,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{The Specification for Matching} - -\begin{bubble}[10cm] -\large -A regular expression \bl{$r$} matches a string~\bl{$s$} -provided -\begin{center} -\bl{$s \in L(r)$} -\end{center} -\end{bubble} - -\bigskip\bigskip - -\ldots and the point of the this lecture is to decide this problem as -fast as possible (unlike Python, Ruby, Java etc) - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Regular Expressions} - -Their inductive definition: - - -\begin{textblock}{6}(2,7.5) - \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} - \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ - & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ - & \bl{$\mid$} & \bl{$c$} & single character\\ - & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ - & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ - & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ - \end{tabular} -\end{textblock} - -\only<2->{\footnotesize -\begin{textblock}{9}(2,0.5) -\begin{bubble}[9.8cm] -\lstinputlisting{../progs/app01.scala} -\end{bubble} -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{ - When Are Two Regular\\[-1mm] - Expressions Equivalent?} - -\large -\begin{center} -\bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Concrete Equivalences} - -\begin{center} -\bl{\begin{tabular}{rcl} -$(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ -$a + a$ & $\equiv$ & $a$\\ -$a + b$ & $\equiv$ & $b + a$\\ -$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\ -$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause -$a \cdot a$ & $\not\equiv$ & $a$\\ -$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\ -\end{tabular}} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Corner Cases} - -\begin{center} -\bl{\begin{tabular}{rcl} -$a \cdot \ZERO$ & $\not\equiv$ & $a$\\ -$a + \ONE$ & $\not\equiv$ & $a$\\ -$\ONE$ & $\equiv$ & $\ZERO^*$\\ -$\ONE^*$ & $\equiv$ & $\ONE$\\ -$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\ -\end{tabular}} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Simplification Rules} - -\begin{center} -\bl{\begin{tabular}{rcl} -$r + \ZERO$ & $\equiv$ & $r$\\ -$\ZERO + r$ & $\equiv$ & $r$\\ -$r \cdot \ONE$ & $\equiv$ & $r$\\ -$\ONE \cdot r$ & $\equiv$ & $r$\\ -$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\ -$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\ -$r + r$ & $\equiv$ & $r$ -\end{tabular}} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Another Homework Question} - -\begin{itemize} -\item How many basic regular expressions are there to match - the string \bl{$abcd$}\,?\pause -\item How many if they cannot include - \bl{$\ONE$} and \bl{$\ZERO$}\/?\pause -\item How many if they are also not - allowed to contain stars?\pause -\item How many if they are also - not allowed to contain \bl{$\_ + \_$}\/? -\end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] \frametitle{\mbox{Brzozowski's Algorithm (1)}} @@ -506,7 +530,7 @@ \bl{$\der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\ & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\ - \bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause + \bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\medskip\bigskip\\\pause \bl{$\ders\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\ @@ -592,7 +616,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Oops\ldots \;\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} +\frametitle{Oops\ldots \boldmath\;$a^{?\{n\}} \cdot a^{\{n\}}$} \begin{center} \begin{tikzpicture} @@ -672,7 +696,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} +\frametitle{Brzozowski: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$} \begin{center} \begin{tikzpicture} @@ -756,7 +780,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} +\frametitle{Brzozowski: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$} \begin{center} \begin{tikzpicture} @@ -789,9 +813,10 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{ - Another Example\\[-1mm] - in Java \liningnums{8} and Python} + Another Example\\[-2mm] + in Java 8, Python and JavaScript} +\bigskip \begin{center} \begin{tikzpicture} \begin{axis}[ @@ -806,12 +831,13 @@ scaled ticks=false, axis lines=left, width=9cm, - height=5cm, - legend entries={Java 8, Python}, + height=5.5cm, + legend entries={Java 8, Python, JavaScript}, legend pos=north west, legend cell align=left] \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; \end{axis} \end{tikzpicture} \end{center} @@ -825,7 +851,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Same Example in Java \liningnums{9}+} +\frametitle{Same Example in Java 9+} \begin{center} \begin{tikzpicture} @@ -905,7 +931,7 @@ \item the algorithm is already quite old; there is still work to be done to use it as a tokenizer (that is relatively new work) -\item we can prove its correctness\ldots +\item we can prove its correctness\ldots (several slides later) \end{itemize} \end{frame} @@ -939,7 +965,7 @@ \underline{Strand 1:} \begin{itemize} -\item Submission on Friday 12 October\\accepted until Monday 15 @ 18:00\medskip +\item Submission on Friday 11 October\\accepted until Monday 14 @ 18:00\medskip \item source code needs to be submitted as well\medskip \item you can re-use my Scala code from KEATS \\ or use any programming language you like\medskip @@ -1031,8 +1057,8 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{\begin{tabular}{c} - Correctness Proof\\[-1mm] for our Matcher\end{tabular}} +\frametitle{Correctness Proof \\[-1mm] + for our Matcher} \begin{itemize} \item We started from @@ -1042,10 +1068,10 @@ & \bl{$s \in L(r)$}\medskip\\ \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause \end{tabular} -\end{center} +\end{center}\bigskip \item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we -have +have\bigskip \begin{center} \begin{tabular}{rp{4cm}} @@ -1177,6 +1203,25 @@ \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Another Homework Question} + + \begin{itemize} + \item How many basic regular expressions are there to match + the string \bl{$abcd$}\,?\pause + \item How many if they cannot include + \bl{$\ONE$} and \bl{$\ZERO$}\/?\pause + \item How many if they are also not + allowed to contain stars?\pause + \item How many if they are also + not allowed to contain \bl{$\_ + \_$}\/? + \end{itemize} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \end{document} %%% Local Variables: