1379 $ _1(_{011}a^* + _1\ONE) $ whereas |
1379 $ _1(_{011}a^* + _1\ONE) $ whereas |
1380 $ \simp(\rup\backslash s) = (_{1011}a^* + _{11}\ONE)$. |
1380 $ \simp(\rup\backslash s) = (_{1011}a^* + _{11}\ONE)$. |
1381 This discrepancy does not appear for the old |
1381 This discrepancy does not appear for the old |
1382 version of $\simp$. |
1382 version of $\simp$. |
1383 |
1383 |
|
1384 Why? |
1384 |
1385 |
1385 During the first derivative operation, |
1386 During the first derivative operation, |
1386 $\rup\backslash a=(_0\ONE + \ZERO)(_0a + _1a^*)$ is |
1387 $\rup\backslash a=( _0[ \ONE\cdot {\bf b}] + _1( _0[ _1\ONE \cdot {\bf a}^*] + [ \ONE \cdot {\bf a}]) )$ |
1387 in the form of a sequence regular expression with |
1388 is in the form of a sequence regular expression with |
1388 two components, the first |
1389 two components, the first |
1389 one $\ONE + \ZERO$ being nullable. |
1390 one $\ONE + \ZERO$ being nullable. |
1390 Recall the simplification function definition: |
1391 Recall again the simplification function definition: |
1391 \begin{center} |
1392 \begin{center} |
1392 \begin{tabular}{@{}lcl@{}} |
1393 \begin{tabular}{@{}lcl@{}} |
1393 |
1394 |
1394 $\textit{simp} \; (\textit{SEQ}\;bs\,a_1\,a_2)$ & $\dn$ & $ (\textit{simp} \; a_1, \textit{simp} \; a_2) \; \textit{match} $ \\ |
1395 $\textit{simp} \; (\textit{SEQ}\;bs\,a_1\,a_2)$ & $\dn$ & $ (\textit{simp} \; a_1, \textit{simp} \; a_2) \; \textit{match} $ \\ |
1395 &&$\quad\textit{case} \; (\ZERO, \_) \Rightarrow \ZERO$ \\ |
1396 &&$\quad\textit{case} \; (\ZERO, \_) \Rightarrow \ZERO$ \\ |
1459 $\rup\backslash a = (_0\ONE + \ZERO)(_0a + _1a^*)$ |
1460 $\rup\backslash a = (_0\ONE + \ZERO)(_0a + _1a^*)$ |
1460 is a sequence |
1461 is a sequence |
1461 with the first component being nullable |
1462 with the first component being nullable |
1462 (unsimplified, unlike the first round of running$\backslash_{simp}$). |
1463 (unsimplified, unlike the first round of running$\backslash_{simp}$). |
1463 Therefore $((_0\ONE + \ZERO)(_0a + _1a^*))\backslash a$ splits into |
1464 Therefore $((_0\ONE + \ZERO)(_0a + _1a^*))\backslash a$ splits into |
|
1465 $\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) ))$ |
|
1466 |
1464 $([(\ZERO + \ZERO)\cdot(_0a + _1a^*)] + _0( _0\ONE + _1[_1\ONE \cdot a^*]))$. |
1467 $([(\ZERO + \ZERO)\cdot(_0a + _1a^*)] + _0( _0\ONE + _1[_1\ONE \cdot a^*]))$. |
1465 After these two successive derivatives without simplification, |
1468 After these two successive derivatives without simplification, |
1466 we apply $\simp$ to this regular expression, which goes through |
1469 we apply $\simp$ to this regular expression, which goes through |
1467 the alternative clause, and each component of |
1470 the alternative clause, and each component of |
1468 $([(\ZERO + \ZERO)\cdot(_0a + _1a^*)] + _0( _0\ONE + _1[_1\ONE \cdot a^*]))$ |
1471 $([(\ZERO + \ZERO)\cdot(_0a + _1a^*)] + _0( _0\ONE + _1[_1\ONE \cdot a^*]))$ |