diff -r 4e221cf587fa -r 0b5f06539a84 handouts/ho03.tex --- a/handouts/ho03.tex Sun Oct 01 15:25:22 2023 +0100 +++ b/handouts/ho03.tex Mon Oct 02 23:10:56 2023 +0100 @@ -562,11 +562,11 @@ \end{figure} \begin{figure}[p] -\small +\small \lstinputlisting[numbers=left,firstline=48,firstnumber=48,lastline=85]{../progs/automata/thompson.sc} \caption{The second part of the Thompson Construction implementing the composition of NFAs according to $\cdot$, $+$ and ${}^*$. - The implicit class (Lines 48--54) about rich partial functions + The extension (Lines 48--54) about rich partial functions implements the infix operation \texttt{+++} which combines an $\epsilon$NFA transition with an NFA transition (both are given as partial functions---but with different type!).\label{thompson2}} @@ -912,8 +912,11 @@ OK\ldots now you know why regular expression matchers in those languages are sometimes so slow. A bit surprising, don't you agree? Also it is still a mystery why Rust, which because of the reasons -above avoids NFAs and uses DFAs instead cannot compete in all cases +above avoids NFAs and uses DFAs instead, cannot compete in all cases with our simple derivative-based regular expression matcher in Scala. +There is an explanation for this as well\ldots{}remember there the +offending examples are of the form $r^{\{n\}}$. Why could they be +a problem in Rust? \subsection*{Subset Construction} @@ -1623,7 +1626,7 @@ \end{center} \noindent -I let you implement this ``automaton''. +You might want to implement this ``automaton''. What do you get? While this makes all sense (modulo the flaw with the infinite states), does this automaton teach us anything new? The answer is no, because it @@ -1634,7 +1637,7 @@ a way to restrict the number of states to something finite. Meaning it would give us a real automaton. However, this would lead us far, far away from what we want -discuss here. +discuss here. The end.