diff -r a10430cb797c -r 3e5f5d19f514 slides/slides02.tex --- a/slides/slides02.tex Wed Oct 07 09:08:55 2020 +0100 +++ b/slides/slides02.tex Sun Oct 11 09:10:08 2020 +0100 @@ -866,6 +866,38 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Brzozowski: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$} + +\begin{center} +\begin{tikzpicture} +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5000,...,10000}, + xmax=11000, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=9cm, + height=7cm, + legend entries={Scala V2,Scala V3,Rust}, + legend pos=north east +] +\addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; +\addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; +\addplot[pink,mark=triangle,mark options={fill=pink}] table {re-rust.data}; +\end{axis} +\end{tikzpicture} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -888,7 +920,7 @@ width=9cm, height=5.5cm, legend entries={Java 8,Python,JavaScript,Swift,Dart}, - legend pos=north west, + legend pos=outer north east, 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}; @@ -1110,6 +1142,56 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\begin{mybox3}{} + der c (r*) def = (der c r) $\cdot$ (r*)\smallskip\\ + Why in the example (slide 19) the first step is: + der a ((a $\cdot$ b) + b)* = (der a ((a $\cdot$ b) + b)) $\cdot$ r\smallskip\\ + and not\smallskip\\ + der a ((a $\cdot$ b) + b) = (der a ((a $\cdot$ b) + b)) ยท (r*) +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + Would it be possible to find and go over a few examples from the + Brzozowski Algorithm, as it doesn't seem to be as simple as it + sounds? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + Is it possible to make a visual example of how using simp() function + on a (a*)*.b regular expression reduces its runtime? If not it's + fine. I am just very surprised that it is so efficient. +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + Do you think the algorithm can be still improved (made faster)? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + Do the regular expression matchers in Python and Java 8 have more + features than the one implemented in this module? Or is there + another reason for their inefficiency? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + Will we discuss the broader Chomsky hierarchy of languages at some + point? +\end{mybox3} +\end{frame} + +\begin{frame}<1-8>[c] +\end{frame} + \end{document} % below are slides for proving.