# HG changeset patch
# User Chengsong
# Date 1562279989 -3600
# Node ID 5df7faf69238af91b0d500b176a4edd09d6781d1
# Parent  866eda9ba66a4235d1cfb07f58d2befb7596f908
added mkeps and pder, still have not proof read it

diff -r 866eda9ba66a -r 5df7faf69238 ninems/ninems.tex
--- 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.