diff -r 68769db65185 -r be599d76f592 handouts/ho01.tex --- a/handouts/ho01.tex Thu Oct 13 12:55:42 2016 +0100 +++ b/handouts/ho01.tex Thu Oct 13 12:57:07 2016 +0100 @@ -225,10 +225,8 @@ legend entries={Python,Ruby}, legend pos=north west, legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] - table {re-python.data}; -\addplot[brown,mark=triangle*, mark options={fill=white}] - table {re-ruby.data}; +\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; +\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data}; \end{axis} \end{tikzpicture} & @@ -248,9 +246,10 @@ axis lines=left, width=5.5cm, height=4.5cm, - legend entries={Java}, + legend entries={Python, Java}, 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}; \end{axis} \end{tikzpicture} @@ -258,19 +257,18 @@ \end{center} \noindent This first graph shows that Python needs approximately 29 -seconds for finding out whether a string of 28 \texttt{a}s -matches the regular expression \texttt{a?\{28\}\,a\{28\}}. -Ruby is even slightly worse.\footnote{In this example Ruby -uses the slightly different regular expression -\texttt{a?a?a?...a?a?aaa...aa}, where the \texttt{a?} and -\texttt{a} each occur $n$ times. More such test cases can be -found at \url{http://www.computerbytesman.com/redos/}.} Simlarly, Java needs approximately -30 seconds to find out that the regular expression $\texttt{(a*)*\,b}$ -does not match strings of 28 \texttt{a}s. -Admittedly, these regular expressions are carefully chosen to -exhibit this exponential behaviour, but similar ones occur -more often than one wants in ``real life''. For example, on 20 -July 2016 a similar regular expression brought the webpage +seconds for finding out whether a string of 28 \texttt{a}s matches the +regular expression \texttt{a?\{28\}\,a\{28\}}. Ruby is even slightly +worse.\footnote{In this example Ruby uses the slightly different + regular expression \texttt{a?a?a?...a?a?aaa...aa}, where the + \texttt{a?} and \texttt{a} each occur $n$ times. More such test + cases can be found at \url{http://www.computerbytesman.com/redos/}.} +Simlarly, Python and Java needs approximately 30 seconds to find out +that the regular expression $\texttt{(a*)*\,b}$ does not match strings +of 28 \texttt{a}s. Admittedly, these regular expressions are +carefully chosen to exhibit this exponential behaviour, but similar +ones occur more often than one wants in ``real life''. For example, on +20 July 2016 a similar regular expression brought the webpage \href{http://stackexchange.com}{Stack Exchange} to its knees: \begin{center}