1706 it can be good if we could express $(r_1 \cdot r_2) \backslash s$ |
1706 it can be good if we could express $(r_1 \cdot r_2) \backslash s$ |
1707 in terms of $r_1 \backslash s_1$ and $r_2 \backslash s_1$, |
1707 in terms of $r_1 \backslash s_1$ and $r_2 \backslash s_1$, |
1708 where $s_1$ is a substring of $s$. |
1708 where $s_1$ is a substring of $s$. |
1709 For this we introduce the $\textit{ders2}$ function, |
1709 For this we introduce the $\textit{ders2}$ function, |
1710 which does a "convolution" on $r_1$ and $r_2$ using the string |
1710 which does a "convolution" on $r_1$ and $r_2$ using the string |
1711 $s$. |
1711 $s$. We omit the bits here as they are not affecting the |
|
1712 structure of the regular expression, and we are mainly |
|
1713 focusing on structure here. |
1712 It is based on the observation that the derivative of $r_1 \cdot r_2$ |
1714 It is based on the observation that the derivative of $r_1 \cdot r_2$ |
1713 with respect to a string $s$ can actually be written in an "explicit form" |
1715 with respect to a string $s$ can actually be written in an "explicit form" |
1714 composed of $r_1$'s derivative of $s$ and $r_2$'s derivative of $s$. |
1716 composed of $r_1$ and $r_2$'s derivatives. |
1715 This can be illustrated in the following procedure execution |
1717 For example, we can look at how $r1\cdot r2$ expands |
1716 \begin{center} |
1718 when being derived with a two-character string: |
1717 $ (r_1 \cdot r_2) \backslash [c_1c_2] = (\textit{if} \; \nullable(r_1)\; \textit{then} \; ((r_1 \backslash c_1) \cdot r_2 + r_2 \backslash c_1) \; \textit{else} \; (r_1\backslash c_1) \cdot r_2) \backslash c_2$ |
1719 \begin{center} |
|
1720 \begin{tabular}{lcl} |
|
1721 $ (r_1 \cdot r_2) \backslash [c_1c_2]$ & $=$ & $ (\textit{if} \; \nullable(r_1)\; \textit{then} \; ((r_1 \backslash c_1) \cdot r_2 + r_2 \backslash c_1) \; \textit{else} \; (r_1\backslash c_1) \cdot r_2) \backslash c_2$\\ |
|
1722 & $=$ & $\textit{if} \; \textit{nullable}(r_1) \;\textit{and} \; \nullable(r_1\backslash c_1) \; \textit{then} \; |
|
1723 (((r_1\backslash c_1c_2)\cdot r_2 +( r_1 \backslash c_1 )\cdot r_2\backslash c_2 )+ r_2 \backslash c_1c_2)$\\ |
|
1724 && $\textit{else if} \; \nullable(r_1) \textit{and} \;\textit{not} \; \nullable(r_1 \backslash c_1)\; \textit{then} \; |
|
1725 ((r_1\backslash c_1c_2)\cdot r_2 + r_2 \backslash c_1c_2)$\\ |
|
1726 && $\textit{else} \;(r_1\backslash c_1c_2) \cdot r_2$ |
|
1727 \end{tabular} |
1718 \end{center} |
1728 \end{center} |
1719 which can also be written in a "convoluted sum" |
1729 which can also be written in a "convoluted sum" |
1720 format: |
1730 format if we omit the order in which the alternatives |
1721 \begin{center} |
1731 are being nested: |
1722 $ (r_1 \cdot r_2) \backslash [c_1c_2] = \sum{r_1 \backslash s_i \cdot r_2 \backslash s_j}$ |
1732 \begin{center} |
|
1733 \begin{tabular}{lcl} |
|
1734 $(r_1 \cdot r_2) \backslash [c_1c_2] $ & $=$ & $\textit{if} \; \textit{nullable}(r_1) \;\textit{and} \; \nullable(r_1\backslash c_1) \; \textit{then} \; |
|
1735 (r_1 \backslash c_1c_2) \cdot r_2 + (r_1 \backslash c_1)\cdot (r_2 \backslash c_2) + r_2 \backslash c_1c_2$\\ |
|
1736 && $\textit{else if} \; \nullable(r_1) \textit{and} \;\textit{not} \; \nullable(r_1 \backslash c_1)\; \textit{then} \; |
|
1737 ((r_1\backslash c_1c_2)\cdot r_2 + r_2 \backslash c_1c_2)$\\ |
|
1738 && $\textit{else} \;(r_1\backslash c_1c_2) \cdot r_2$\\ |
|
1739 & $=$ & $\sum\limits{s_i }{r_1 \backslash s_i \cdot r_2 \backslash s_j} \; \text{where} \; s_i \; \text{is} \; \text{true prefix}\; \text{of} \; s \;\text{and} \; s_i @s_j = s \; \text{and} \;\nullable(r_1\backslash s_i)$ |
|
1740 \end{tabular} |
1723 \end{center} |
1741 \end{center} |
1724 In a more serious manner, we should write |
1742 In a more serious manner, we should write |
1725 \begin{center} |
1743 \begin{center} |
1726 $ (r_1 \cdot r_2) \backslash [c_1c_2] = \sum{r_1 \backslash s_i \cdot r_2 \backslash s_j}$ |
1744 $ (r_1 \cdot r_2) \backslash [c_1c_2] = \sum{r_1 \backslash s_i \cdot r_2 \backslash s_j}$ |
1727 \end{center} |
1745 \end{center} |