# HG changeset patch # User Christian Urban # Date 1602403808 -3600 # Node ID 3e5f5d19f514b7af956fa7fe56f0cfc54087d21c # Parent a10430cb797c0e259c1c4523954032fd1fa2efc1 updated diff -r a10430cb797c -r 3e5f5d19f514 data.sty --- a/data.sty Wed Oct 07 09:08:55 2020 +0100 +++ b/data.sty Sun Oct 11 09:10:08 2020 +0100 @@ -73,6 +73,21 @@ 28 34.79653 \end{filecontents} +%% example a?{n} a{n} +\begin{filecontents}{re-rust.data} +1000 0.95 +1500 2.17 +2000 3.9 +2100 4.121 +2150 4.3 +2180 14.9 +2200 15 +2500 18 +3000 24 +3500 31 +4000 40 +\end{filecontents} + % JavaScript, example (a*)*b \begin{filecontents}{re-js.data} 5 0.061 diff -r a10430cb797c -r 3e5f5d19f514 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r a10430cb797c -r 3e5f5d19f514 handouts/ho04.tex --- a/handouts/ho04.tex Wed Oct 07 09:08:55 2020 +0100 +++ b/handouts/ho04.tex Sun Oct 11 09:10:08 2020 +0100 @@ -907,7 +907,7 @@ \begin{figure}[t] \begin{center} -\mbox{\lstinputlisting[language=while]{../progs/fib.while}} +\mbox{\lstinputlisting[language=while]{../progs/while-tests/fib.while}} \end{center} \caption{The Fibonacci program in the While-language.\label{while}} \end{figure} diff -r a10430cb797c -r 3e5f5d19f514 hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r a10430cb797c -r 3e5f5d19f514 hws/hw03.tex --- a/hws/hw03.tex Wed Oct 07 09:08:55 2020 +0100 +++ b/hws/hw03.tex Sun Oct 11 09:10:08 2020 +0100 @@ -120,7 +120,7 @@ \end{tikzpicture} \end{center} -\item \textbf{(Deleted for 2017, 2018, 2019)} +\item %%\textbf{(Deleted for 2017, 2018, 2019)} Given the following deterministic finite automaton over the alphabet $\{0, 1\}$, find the corresponding minimal automaton. In case states can be merged, state clearly which states can be merged. diff -r a10430cb797c -r 3e5f5d19f514 slides/slides01.tex --- a/slides/slides01.tex Wed Oct 07 09:08:55 2020 +0100 +++ b/slides/slides01.tex Sun Oct 11 09:10:08 2020 +0100 @@ -1577,6 +1577,9 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Questions \begin{frame}[c] \begin{mybox3}{} diff -r a10430cb797c -r 3e5f5d19f514 slides/slides02.pdf Binary file slides/slides02.pdf has changed 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. diff -r a10430cb797c -r 3e5f5d19f514 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r a10430cb797c -r 3e5f5d19f514 slides/slides03.tex --- a/slides/slides03.tex Wed Oct 07 09:08:55 2020 +0100 +++ b/slides/slides03.tex Sun Oct 11 09:10:08 2020 +0100 @@ -190,8 +190,8 @@ \begin{center} \begin{tabular}{l} -\bl{$\widehat{\delta}(q, []) \dn q$}\\ -\bl{$\widehat{\delta}(q, c::s) \dn \widehat{\delta}(\delta(q, c), s)$}\\ +\bl{$\widehat{\delta}(Q, []) \dn Q$}\\ +\bl{$\widehat{\delta}(Q, c::s) \dn \widehat{\delta}(\delta(Q, c), s)$}\\ \end{tabular} \end{center}\pause