124 \texttt{re.scala} template file. As usual you have to |
124 \texttt{re.scala} template file. As usual you have to |
125 prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}. |
125 prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}. |
126 Since some tasks are time sensitive, you can check the reference |
126 Since some tasks are time sensitive, you can check the reference |
127 implementation as follows: if you want to know, for example, how long it takes |
127 implementation as follows: if you want to know, for example, how long it takes |
128 to match strings of $a$'s using the regular expression $(a^*)^*\cdot b$ |
128 to match strings of $a$'s using the regular expression $(a^*)^*\cdot b$ |
129 you can querry as follows: |
129 you can query as follows: |
130 |
130 |
131 |
131 |
132 |
132 |
133 \begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] |
133 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] |
134 $ scala -cp re.jar |
134 $ scala -cp re.jar |
135 scala> import CW9a._ |
135 scala> import CW9a._ |
136 scala> for (i <- 0 to 5000000 by 500000) { |
136 scala> for (i <- 0 to 5000000 by 500000) { |
137 | println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.") |
137 | println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.") |
138 | } |
138 | } |
229 \end{tabular} |
229 \end{tabular} |
230 \end{center}~\hfill[1 Mark] |
230 \end{center}~\hfill[1 Mark] |
231 |
231 |
232 \item[(2)] Implement a function, called \textit{der}, by recursion over |
232 \item[(2)] Implement a function, called \textit{der}, by recursion over |
233 regular expressions. It takes a character and a regular expression |
233 regular expressions. It takes a character and a regular expression |
234 as arguments and calculates the derivative regular expression according |
234 as arguments and calculates the derivative of a xregular expression according |
235 to the rules: |
235 to the rules: |
236 |
236 |
237 \begin{center} |
237 \begin{center} |
238 \begin{tabular}{lcl} |
238 \begin{tabular}{lcl} |
239 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\ |
239 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\ |
306 For example the regular expression |
306 For example the regular expression |
307 \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] |
307 \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] |
308 |
308 |
309 simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be |
309 simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be |
310 seen as trees and there are several methods for traversing |
310 seen as trees and there are several methods for traversing |
311 trees. One of them corresponds to the inside-out traversal, which is |
311 trees. One of them corresponds to the inside-out traversal, which is also |
312 sometimes also called post-order traversal: you traverse inside the |
312 sometimes called post-order tra\-versal: you traverse inside the |
313 tree and on the way up you apply simplification rules. |
313 tree and on the way up you apply simplification rules. |
314 Furthermore, |
314 \textbf{Another Hint:} |
315 remember numerical expressions from school times: there you had expressions |
315 Remember numerical expressions from school times---there you had expressions |
316 like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$ |
316 like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$ |
317 and simplification rules that looked very similar to rules |
317 and simplification rules that looked very similar to rules |
318 above. You would simplify such numerical expressions by replacing |
318 above. You would simplify such numerical expressions by replacing |
319 for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then |
319 for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then |
320 look whether more rules are applicable. If you organise the |
320 look whether more rules are applicable. If you organise the |
376 \[ |
376 \[ |
377 \texttt{SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)} |
377 \texttt{SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)} |
378 \] |
378 \] |
379 |
379 |
380 \noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested |
380 \noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested |
381 50 or more times.\\ |
381 50 or more times?\\ |
382 \mbox{}\hfill[1 Mark] |
382 \mbox{}\hfill[1 Mark] |
383 \end{itemize} |
383 \end{itemize} |
384 |
384 |
385 \subsection*{Background} |
385 \subsection*{Background} |
386 |
386 |