639 \noindent Now we are talking business! The modified matcher can within

   639 \noindent Now we are talking business! The modified matcher can within

   640 25 seconds handle regular expressions up to $n = 1,100$ before a

   640 25 seconds handle regular expressions up to $n = 1,100$ before a

   641 StackOverflow is raised. Recall that Python and Ruby (and our first

   641 StackOverflow is raised. Recall that Python and Ruby (and our first

   642 version, Scala V1) could only handle $n = 27$ or so in 30

   642 version, Scala V1) could only handle $n = 27$ or so in 30

   643 seconds. We have not tried our algorithm on the second example $(a^*)^* \cdot

   643 seconds. We have not tried our algorithm on the second example $(a^*)^* \cdot

   645 

   645 

   646 

   646 

   647 The moral is that our algorithm is rather sensitive to the

   647 The moral is that our algorithm is rather sensitive to the

   648 size of regular expressions it needs to handle. This is of

   648 size of regular expressions it needs to handle. This is of

   649 course obvious because both $\textit{nullable}$ and $\textit{der}$ frequently

   649 course obvious because both $\textit{nullable}$ and $\textit{der}$ frequently

   729 To recap, Python and Ruby needed approximately 30 seconds to match a

   729 To recap, Python and Ruby needed approximately 30 seconds to match a

   730 string of 28 \texttt{a}s and the regular expression $a^{?\{n\}} \cdot

   730 string of 28 \texttt{a}s and the regular expression $a^{?\{n\}} \cdot

   731 a^{\{n\}}$.  We need a third of this time to do the same with strings

   731 a^{\{n\}}$.  We need a third of this time to do the same with strings

   732 up to 11,000 \texttt{a}s.  Similarly, Java and Python needed 30

   732 up to 11,000 \texttt{a}s.  Similarly, Java and Python needed 30

   733 seconds to find out the regular expression $(a^*)^* \cdot b$ does not

   733 seconds to find out the regular expression $(a^*)^* \cdot b$ does not

   735 for strings composed of nearly 6,000,000 \texttt{a}s:

   735 for strings composed of nearly 6,000,000 \texttt{a}s:

   736 

   736 

   737 

   737 

   738 \begin{center}

   738 \begin{center}

   739 \begin{tikzpicture}

   739 \begin{tikzpicture}