--- a/ninems/ninems.tex Thu Jul 04 23:27:32 2019 +0100
+++ b/ninems/ninems.tex Thu Jul 04 23:39:49 2019 +0100
@@ -464,9 +464,17 @@
is matched the empty regular expression $r_n$. This function is defined
as
-$mkeps $ $1 \,[] $ $= Empty$
-......
-
+ \begin{center}
+ \begin{tabular}{lcl}
+ $\mkeps(\ONE)$ & $\dn$ & $\Empty$ \\
+ $\mkeps(r_{1}+r_{2})$ & $\dn$
+ & \textit{if} $\nullable(r_{1})$\\
+ & & \textit{then} $\Left(\mkeps(r_{1}))$\\
+ & & \textit{else} $\Right(\mkeps(r_{2}))$\\
+ $\mkeps(r_1\cdot r_2)$ & $\dn$ & $\Seq\,(\mkeps\,r_1)\,(\mkeps\,r_2)$\\
+ $mkeps(r^*)$ & $\dn$ & $\Stars\,[]$
+ \end{tabular}
+ \end{center}
After this, we inject back the characters one by one in order to build
the parse tree $v_i$ for how the regex $r_i$ matches the string
@@ -541,6 +549,14 @@
Antimirov defined the "partial derivatives" of regular expressions to be this:
%TODO definition of partial derivatives
+\[ pder c 0 = emtpy set\]
+\[pder c 1 = emptry set\]
+\[pder c c = if c is equal to d then set containing lambda only else empty set\]
+\[pder c r_1+r_2 = pder c r_1 \cup pder c r_2\]
+\[pder c r_1 \cdot r_2 = if r_1 nullable then set of r \cdot r_2' where r is in pder c r_1 \cup pder c r_2\]
+\[else set of r \cdot r_2' where r is in pder c r_1\]
+\[pder c r^* = set of r \cdot r^* where r \in pder c r\]
+
it is essentially a set of regular expressions that come from the sub-structure of the original regular expression.
Antimirov has proved a nice size bound of the size of partial derivatives. Roughly speaking the size will not exceed the fourth power of the number of nodes in that regular expression. Interestingly, we observed from experiment that after the simplification step, our regular expression has the same size or is smaller than the partial derivatives. This allows us to prove a tight bound on the size of regular expression during the running time of the algorithm if we can establish the connection between our simplification rules and partial derivatives.