131 

   131 

   132 \noindent Again I leave it to you to make sure you agree

   132 \noindent Again I leave it to you to make sure you agree

   133 with these equivalences and non-equivalences. 

   133 with these equivalences and non-equivalences. 

   134 

   134 

   135 

   135 

   137 equivalences will play an important role:

   137 equivalences will play an important role:

   138 

   138 

   139 \begin{center}

   139 \begin{center}

   140 \begin{tabular}{rcl}

   140 \begin{tabular}{rcl}

   141 $r + \varnothing$  & $\equiv$ & $r$\\

   141 $r + \varnothing$  & $\equiv$ & $r$\\

   331 \end{tabular}

   331 \end{tabular}

   332 \end{center}

   332 \end{center}

   333 

   333 

   334 \noindent Again the operation $Der$ might help to rationalise

   334 \noindent Again the operation $Der$ might help to rationalise

   335 this algorithm. We want to know whether $abc \in L(r_1)$. We

   335 this algorithm. We want to know whether $abc \in L(r_1)$. We

   337 builds the set where all the strings not starting with $a$ are

   337 builds the set where all the strings not starting with $a$ are

   338 filtered out. Of the remaining strings, the $a$ is stripped

   338 filtered out. Of the remaining strings, the $a$ is stripped

   339 off. Then we continue with filtering out all strings not

   339 off. Then we continue with filtering out all strings not

   340 starting with $b$ and stripping off the $b$ from the remaining

   340 starting with $b$ and stripping off the $b$ from the remaining

   341 strings, that means we build $Der\,b\,(Der\,a\,(L(r_1)))$.

   341 strings, that means we build $Der\,b\,(Der\,a\,(L(r_1)))$.

   505 

   505 

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

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

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

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

   508 course obvious because both $nullable$ and $der$ need to

   508 course obvious because both $nullable$ and $der$ need to

   509 traverse the whole regular expression. There seems to be one

   509 traverse the whole regular expression. There seems to be one

   511 function often produces ``useless'' $\varnothing$s and

   511 function often produces ``useless'' $\varnothing$s and

   512 $\epsilon$s. To see this, consider $r = ((a \cdot b) + b)^*$

   512 $\epsilon$s. To see this, consider $r = ((a \cdot b) + b)^*$

   513 and the following two derivatives

   513 and the following two derivatives

   514 

   514 

   515 \begin{center}

   515 \begin{center}