1374 $(ab+(a^*+aa))$ and $s$ is the string $aa$ |
1374 $(ab+(a^*+aa))$ and $s$ is the string $aa$ |
1375 \end{center} |
1375 \end{center} |
1376 |
1376 |
1377 \noindent |
1377 \noindent |
1378 $\rup\backslash_{simp} \, s$ is equal to |
1378 $\rup\backslash_{simp} \, s$ is equal to |
1379 $ _1(_{11}a^* + _0\ONE) $ |
1379 $ _1(_{011}a^* + _1\ONE) $ whereas |
1380 $\rup\backslash_{simp} \, s \neq \simp(\rup\backslash s)$, |
1380 $ \simp(\rup\backslash s) = (_{1011}a^* + _{11}\ONE)$. |
1381 whereas this does not happen for the old |
1381 This discrepancy does not appear for the old |
1382 version of $\simp$. |
1382 version of $\simp$. |
|
1383 |
|
1384 Why? |
|
1385 |
|
1386 During the first derivative operation, |
|
1387 \begin{center} |
|
1388 $\rup\backslash a=( _0[ \ONE\cdot {\bf b}] + _1( _0[ _1\ONE \cdot {\bf a}^*] + [ \ONE \cdot {\bf a}]) )$, |
|
1389 \end{center} |
|
1390 \noindent |
|
1391 the second derivative gives us |
|
1392 \begin{center} |
|
1393 $\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) ))$, |
|
1394 \end{center} |
|
1395 |
|
1396 \noindent |
|
1397 and this simplifies to |
|
1398 \begin{center} |
|
1399 $ _1(_{011}{\bf a}^* + _1\ONE) $ |
|
1400 \end{center} |
|
1401 |
|
1402 If, after the first derivative we apply simplification we get |
|
1403 $(_0{\bf b} + _{101}{\bf a}^* + _{11}{\bf a} )$, |
|
1404 and we do another derivative, getting |
|
1405 $(\ZERO + (_{101}(\ONE \cdot _1{\bf a}^*)+_{11}\ONE)$, |
|
1406 which simplifies to |
|
1407 \begin{center} |
|
1408 $ (_{1011}a^* + _{11}\ONE) $ |
|
1409 \end{center} |
|
1410 |
|
1411 |
|
1412 |
|
1413 |
|
1414 |
1383 We have changed the algorithm to suppress the old |
1415 We have changed the algorithm to suppress the old |
1384 counterexample, but this gives rise to new counterexamples. |
1416 counterexample, but this gives rise to new counterexamples. |
1385 This dilemma causes this amendment not a successful |
1417 This dilemma causes this amendment not a successful |
1386 attempt to make $\rup\backslash_{simp} \, s = \simp(\rup\backslash s)$ |
1418 attempt to make $\rup\backslash_{simp} \, s = \simp(\rup\backslash s)$ |
1387 under every possible regular expression and string. |
1419 under every possible regular expression and string. |