equal
deleted
inserted
replaced
263 rule is applied. Our matching algorithm in the next section |
263 rule is applied. Our matching algorithm in the next section |
264 will often generate such ``useless'' $\ONE$s and |
264 will often generate such ``useless'' $\ONE$s and |
265 $\ZERO$s, therefore simplifying them away will make the |
265 $\ZERO$s, therefore simplifying them away will make the |
266 algorithm quite a bit faster. |
266 algorithm quite a bit faster. |
267 |
267 |
|
268 Finally here are three equivalences between regulare expressions which are |
|
269 not so obvious: |
|
270 |
|
271 \begin{center} |
|
272 \begin{tabular}{rcl} |
|
273 $r^*$ & $\equiv$ & $1 + r\cdot r^*$\\ |
|
274 $(r_1 + r_2)^*$ & $\equiv$ & $r_1^* \cdot (r_2\cdot r_1^*)^*$\\ |
|
275 $(r_1 \cdot r_2)^*$ & $\equiv$ & $1 + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\ |
|
276 \end{tabular} |
|
277 \end{center} |
|
278 |
|
279 \noindent |
|
280 You can try to establish them. As an aside, there has been a lot of research |
|
281 in questions like: Can one always decide when two regular expressions are |
|
282 equivalent or not? What does an algorithm look like to decide this? |
|
283 |
268 \subsection*{The Matching Algorithm} |
284 \subsection*{The Matching Algorithm} |
269 |
285 |
270 The algorithm we will define below consists of two parts. One |
286 The algorithm we will define below consists of two parts. One |
271 is the function $\textit{nullable}$ which takes a regular expression as |
287 is the function $\textit{nullable}$ which takes a regular expression as |
272 argument and decides whether it can match the empty string |
288 argument and decides whether it can match the empty string |