256 can view them as \emph{simplification rules}. Consider for |
256 can view them as \emph{simplification rules}. Consider for |
257 example the regular expression |
257 example the regular expression |
258 |
258 |
259 \begin{equation} |
259 \begin{equation} |
260 (r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO) |
260 (r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO) |
261 \label{big} |
261 \label{bbbig} |
262 \end{equation} |
262 \end{equation} |
263 |
263 |
264 \noindent If we can find an equivalent regular expression that is |
264 \noindent If we can find an equivalent regular expression that is |
265 simpler (that usually means smaller), then this might potentially make |
265 simpler (that usually means smaller), then this might potentially make |
266 our matching algorithm run faster. We can look for such a simpler, but |
266 our matching algorithm run faster. We can look for such a simpler, but |
267 equivalent, regular expression $r'$ because whether a string $s$ is in |
267 equivalent, regular expression $r'$ because whether a string $s$ is in |
268 $L(r)$ or in $L(r')$ does not matter as long as $r\equiv r'$. Yes? \footnote{You have checked this for yourself? Your friendly lecturer might talk rubbish\ldots{}one never knows.} |
268 $L(r)$ or in $L(r')$ does not matter as long as $r\equiv r'$. Yes? \footnote{You have checked this for yourself? Your friendly lecturer might talk rubbish\ldots{}one never knows.} |
269 |
269 |
270 In the example above you will see that the regular expression in |
270 In the example above you will see that the regular expression in |
271 \eqref{big} is equivalent to just $r_1$. You can verify this by |
271 \eqref{bbbig} is equivalent to just $r_1$. You can verify this by |
272 iteratively applying the simplification rules from above: |
272 iteratively applying the simplification rules from above: |
273 |
273 |
274 \begin{center} |
274 \begin{center} |
275 \begin{tabular}{ll} |
275 \begin{tabular}{ll} |
276 & $(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot |
276 & $(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot |
622 |
622 |
623 We can however fix this easily by having an explicit constructor for |
623 We can however fix this easily by having an explicit constructor for |
624 $r^{\{n\}}$. In Scala we would introduce a constructor like |
624 $r^{\{n\}}$. In Scala we would introduce a constructor like |
625 |
625 |
626 \begin{center} |
626 \begin{center} |
627 \code{case class NTIMES(r: Rexp, n: Int) extends Rexp} |
627 \code{case NTIMES(r: Rexp, n: Int)} |
628 \end{center} |
628 \end{center} |
629 |
629 |
630 \noindent With this fix we have a constant ``size'' regular expression |
630 \noindent With this fix we have a constant ``size'' regular expression |
631 for our running example no matter how large $n$ is (see the |
631 for our running example no matter how large $n$ is (see the |
632 \texttt{size} section in the implementations). This means we have to |
632 \texttt{size} section in the implementations). This means we have to |