# HG changeset patch # User Christian Urban # Date 1538352702 -3600 # Node ID b153c04834ebfb1a0e6b8347ed60de0dc2082575 # Parent 2be8c4c77418f0b45c522186d68e5228f7af59dd updated diff -r 2be8c4c77418 -r b153c04834eb handouts/graphs.pdf Binary file handouts/graphs.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho02.tex --- a/handouts/ho02.tex Sun Sep 30 23:38:38 2018 +0100 +++ b/handouts/ho02.tex Mon Oct 01 01:11:42 2018 +0100 @@ -278,7 +278,7 @@ \end{center} \noindent -We will not use them in our algorithm, but feel free to convince you +We will not use them in our algorithm, but feel free to convince yourself that they hold. As an aside, there has been a lot of research about questions like: Can one always decide when two regular expressions are equivalent or not? What does an algorithm look like to decide this @@ -478,10 +478,10 @@ whether the claim holds any water is a different question, which for example is the point of the Strand-2 Coursework. -This algorithm was introduced by Janus Brzozowski in 1964, but +This algorithm was introduced by Janusz Brzozowski in 1964, but is more widely known only in the last 10 or so years. Its main attractions are simplicity and being fast, as well as -being easily extendable for other regular expressions such as +being easily extendible for other regular expressions such as $r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of Strand-1 Coursework 1). @@ -543,7 +543,7 @@ %StackOverflow exception, but still\ldots For running the algorithm with our first example, the evil -regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement +regular expression $a^?{}^{\{n\}}\cdot a^{\{n\}}$, we need to implement the optional regular expression and the `exactly $n$-times regular expression'. This can be done with the translations @@ -697,7 +697,7 @@ calls \texttt{der} first, but then simplifies the resulting derivative regular expressions before building the next derivative, see -Line~\ref{simpline}.\label{scala2}} +Line~24.\label{scala2}} \end{figure} \begin{center} @@ -729,10 +729,11 @@ To recap, Python and Ruby needed approximately 30 seconds to match a string of 28 \texttt{a}s and the regular expression $a^{?\{n\}} \cdot a^{\{n\}}$. We need a third of this time to do the same with strings -up to 11,000 \texttt{a}s. Similarly, Java and Python needed 30 +up to 11,000 \texttt{a}s. Similarly, Java 8 and Python needed 30 seconds to find out the regular expression $(a^*)^* \cdot b$ does not -match the string of 28 \texttt{a}s. We can do the same in the same amount of time -for strings composed of nearly 6,000,000 \texttt{a}s: +match the string of 28 \texttt{a}s. In Java 9 and later this has been +cranked up to 39,000 \texttt{a}s, but we can do the same in the same +amount of time for strings composed of nearly 6,000,000 \texttt{a}s: \begin{center} @@ -1046,13 +1047,13 @@ recipes} is already a big step in actually performing these proofs. If you do not believe it, proofs have helped me to make sure my code is correct and in several instances prevented me of letting slip -embarrassing mistakes into the `wild'. +embarrassing mistakes into the `wild'. \end{document} - +% !TeX program = latexmk -xelatex %%% Local Variables: %%% mode: latex %%% TeX-master: t diff -r 2be8c4c77418 -r b153c04834eb handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho07.pdf Binary file handouts/ho07.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb progs/re2.scala --- a/progs/re2.scala Sun Sep 30 23:38:38 2018 +0100 +++ b/progs/re2.scala Mon Oct 01 01:11:42 2018 +0100 @@ -122,3 +122,5 @@ size(ders("aaaa".toList, EVIL2)) // 116 size(ders("aaaaa".toList, EVIL2)) // 230 size(ders("aaaaaa".toList, EVIL2)) // 456 + +size(ders(("a" * 20).toList, EVIL2)) // 7340068 \ No newline at end of file diff -r 2be8c4c77418 -r b153c04834eb progs/re3.scala --- a/progs/re3.scala Sun Sep 30 23:38:38 2018 +0100 +++ b/progs/re3.scala Mon Oct 01 01:11:42 2018 +0100 @@ -129,13 +129,6 @@ size(ders("aaaaa".toList, EVIL2)) // 8 -// test: ("a" | "aa")* -val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) - -for (i <- 1 to 29 by 1) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i))) + - " size: " + size(ders(("a" * i).toList, EVIL3))) -} diff -r 2be8c4c77418 -r b153c04834eb slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides02.tex --- a/slides/slides02.tex Sun Sep 30 23:38:38 2018 +0100 +++ b/slides/slides02.tex Mon Oct 01 01:11:42 2018 +0100 @@ -270,6 +270,19 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}} + +\bigskip +homework (written exam 80\%)\\ +coursework (20\%; first one today)\\ +submission Fridays @ 18:00 -- accepted Mondays +\mbox{} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{Semantic Derivative\\[5mm]} @@ -880,6 +893,45 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Negation of Regular Expr's} + +\begin{itemize} +\item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip +\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip +\item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip +\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$} +\end{itemize}\bigskip\pause + +Used often for recognising comments: + +\[ +\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} +\] + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Coursework} + +\underline{Strand 1:} + +\begin{itemize} +\item Submission on Friday 12 October\\accepted until Monday 15 @ 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 +\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{Proofs about Rexps} diff -r 2be8c4c77418 -r b153c04834eb slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides07.pdf Binary file slides/slides07.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides10.pdf Binary file slides/slides10.pdf has changed diff -r 2be8c4c77418 -r b153c04834eb slides/slides11.pdf Binary file slides/slides11.pdf has changed