diff -r d9d2da923b7f -r 788f4aa28bc5 etnms/20200205.tex --- a/etnms/20200205.tex Thu Feb 06 10:49:23 2020 +0000 +++ b/etnms/20200205.tex Sat Feb 08 21:34:50 2020 +0000 @@ -1384,100 +1384,31 @@ Why? During the first derivative operation, -$\rup\backslash a=( _0[ \ONE\cdot {\bf b}] + _1( _0[ _1\ONE \cdot {\bf a}^*] + [ \ONE \cdot {\bf a}]) )$ -is in the form of a sequence regular expression with -two components, the first -one $\ONE + \ZERO$ being nullable. -Recall again the simplification function definition: \begin{center} - \begin{tabular}{@{}lcl@{}} - - $\textit{simp} \; (\textit{SEQ}\;bs\,a_1\,a_2)$ & $\dn$ & $ (\textit{simp} \; a_1, \textit{simp} \; a_2) \; \textit{match} $ \\ - &&$\quad\textit{case} \; (\ZERO, \_) \Rightarrow \ZERO$ \\ - &&$\quad\textit{case} \; (\_, \ZERO) \Rightarrow \ZERO$ \\ - &&$\quad\textit{case} \; (\ONE, a_2') \Rightarrow \textit{fuse} \; bs \; a_2'$ \\ - &&$\quad\textit{case} \; (a_1', \ONE) \Rightarrow \textit{fuse} \; bs \; a_1'$ \\ - &&$\quad\textit{case} \; (a_1', a_2') \Rightarrow \textit{SEQ} \; bs \; a_1' \; a_2'$ \\ - - $\textit{simp} \; (\textit{ALTS}\;bs\,as)$ & $\dn$ & $\textit{distinct}( \textit{flatten} ( \textit{map simp as})) \; \textit{match} $ \\ - &&$\quad\textit{case} \; [] \Rightarrow \ZERO$ \\ - &&$\quad\textit{case} \; a :: [] \Rightarrow \textit{fuse bs a}$ \\ - &&$\quad\textit{case} \; as' \Rightarrow \textit{ALTS}\;bs\;as'$\\ - - $\textit{simp} \; a$ & $\dn$ & $\textit{a} \qquad \textit{otherwise}$ -\end{tabular} -\end{center} +$\rup\backslash a=( _0[ \ONE\cdot {\bf b}] + _1( _0[ _1\ONE \cdot {\bf a}^*] + [ \ONE \cdot {\bf a}]) )$, +\end{center} +\noindent + the second derivative gives us + \begin{center} +$\rup\backslash a=(_0( [\ZERO\cdot {\bf b}] + 0) + _1( _0( [\ZERO\cdot {\bf a}^*] + _1[ _1\ONE \cdot {\bf a}^*]) + _1( [\ZERO \cdot {\bf a}] + \ONE) ))$, +\end{center} \noindent - -and the difinition of $\flatten$: - \begin{center} - \begin{tabular}{c c c} - $\flatten \; []$ & $\dn$ & $[]$\\ - $\flatten \; \ZERO::rs$ & $\dn$ & $rs$\\ - $\flatten \;(_{\textit{bs}_1}\oplus \textit{rs}_1 ::rs)$ & $\dn$ & $(\map \, (\fuse \, \textit{bs}_1) \,\textit{rs}_1) ::: \flatten(rs)$\\ - $\flatten \; r :: rs$ & $\dn$ & $r::\flatten(rs)$ - \end{tabular} - \end{center} - - \noindent - -If we call $\simp$ on $\rup\backslash a$, -then we would go throught the third clause of -the sequence case:$\quad\textit{case} \; (\ONE, a_2') \Rightarrow \textit{fuse} \; bs \; a_2'$. -The $\ZERO$ of $(_0\ONE + \ZERO)$ is thrown away -by $\flatten$ and -$_0\ONE$ merged into $(_0a + _1a^*)$ by simply -putting its bits($_0$) to the front of the second component: - ${\bf_0}(_0a + _1a^*)$. - After a second derivative operation, - namely, $(_0(_0a + _1a^*))\backslash a$, we get - $ - _0(_0 \ONE + _1(_1\ONE \cdot a^*)) - $, and this simplifies to $_0(_0 \ONE + _{11} a^*)$ - by the third clause of the alternative case: - $\quad\textit{case} \; as' \Rightarrow \textit{ALTS}\;bs\;as'$. -The outmost bit $_0$ stays with -the outmost regular expression, rather than being fused to -its child regular expressions, as what we will later see happens -to $\simp(\rup\backslash \, s)$. -If we choose to not simplify in the midst of derivative operations, -but only do it at the end after the string has been exhausted, -namely, $\simp(\rup\backslash \, s)=\simp((\rup\backslash a)\backslash a)$, -then at the {\bf second} derivative of -$(\rup\backslash a)\bf{\backslash a}$ -we will go throught the clause of $\backslash$: +and this simplifies to \begin{center} -\begin{tabular}{lcl} -$(\textit{SEQ}\;bs\,a_1\,a_2)\,\backslash c$ & $\dn$ & - $(when \; \textit{bnullable}\,a_1)$\\ - & &$\textit{ALTS}\,bs\,List(\;\;(\textit{SEQ}\,[]\,(a_1\,\backslash c)\,a_2),$\\ - & &$(\textit{fuse}\,(\textit{bmkeps}\,a_1)\,(a_2\,\backslash c))\;\;)$\\ -\end{tabular} +$ _1(_{011}{\bf a}^* + _1\ONE) $ \end{center} -because -$\rup\backslash a = (_0\ONE + \ZERO)(_0a + _1a^*)$ -is a sequence -with the first component being nullable -(unsimplified, unlike the first round of running$\backslash_{simp}$). -Therefore $((_0\ONE + \ZERO)(_0a + _1a^*))\backslash a$ splits into -$\rup\backslash a=(_0( [\ZERO\cdot {\bf b}] + 0) + _1( _0( [\ZERO\cdot a^*] + _1[ _1\ONE \cdot {\bf a}^*]) + _1( [\ZERO \cdot {\bf a}] + \ONE) ))$ +If, after the first derivative we apply simplification we get +$(_0{\bf b} + _{101}{\bf a}^* + _{11}{\bf a} )$, +and we do another derivative, getting +$(\ZERO + (_{101}(\ONE \cdot _1{\bf a}^*)+_{11}\ONE)$, +which simplifies to +\begin{center} +$ (_{1011}a^* + _{11}\ONE) $ +\end{center} -$([(\ZERO + \ZERO)\cdot(_0a + _1a^*)] + _0( _0\ONE + _1[_1\ONE \cdot a^*]))$. -After these two successive derivatives without simplification, -we apply $\simp$ to this regular expression, which goes through -the alternative clause, and each component of -$([(\ZERO + \ZERO)\cdot(_0a + _1a^*)] + _0( _0\ONE + _1[_1\ONE \cdot a^*]))$ -will be simplified, giving us the list:$[\ZERO, _0(_0\ONE + _{11}a^*)]$ -This list is then "flattened"--$\ZERO$ will be -thrown away by $\textit{flatten}$; $ _0(_0\ONE + _{11}a^*)$ -is opened up to make the list consisting of two separate elements -$_{00}\ONE$ and $_{011}a^*$, note that $flatten$ -$\fuse$s the bit(s) $_0$ to the front of $_0\ONE $ and $_{11}a^*$. -The order of simplification, which impacts the order that alternatives -are opened up, causes -the bits to be moved differently. +