231 language). |
231 language). |
232 |
232 |
233 The other function of our matching algorithm calculates a |
233 The other function of our matching algorithm calculates a |
234 \emph{derivative} of a regular expression. This is a function |
234 \emph{derivative} of a regular expression. This is a function |
235 which will take a regular expression, say $r$, and a |
235 which will take a regular expression, say $r$, and a |
236 character, say $c$, as argument and return a new regular |
236 character, say $c$, as argument and returns a new regular |
237 expression. Be careful that the intuition behind this function |
237 expression. Be careful that the intuition behind this function |
238 is not so easy to grasp on first reading. Essentially this |
238 is not so easy to grasp on first reading. Essentially this |
239 function solves the following problem: if $r$ can match a |
239 function solves the following problem: if $r$ can match a |
240 string of the form $c\!::\!s$, what does the regular |
240 string of the form $c\!::\!s$, what does the regular |
241 expression look like that can match just $s$? The definition |
241 expression look like that can match just $s$? The definition |
269 matched. Next come the recursive cases, which are a bit more |
269 matched. Next come the recursive cases, which are a bit more |
270 involved. Fortunately, the $+$-case is still relatively |
270 involved. Fortunately, the $+$-case is still relatively |
271 straightforward: all strings of the form $c\!::\!s$ are either |
271 straightforward: all strings of the form $c\!::\!s$ are either |
272 matched by the regular expression $r_1$ or $r_2$. So we just |
272 matched by the regular expression $r_1$ or $r_2$. So we just |
273 have to recursively call $der$ with these two regular |
273 have to recursively call $der$ with these two regular |
274 expressions and compose the results again with $+$. Yes, makes |
274 expressions and compose the results again with $+$. Makes |
275 sense? The $\cdot$-case is more complicated: if $r_1\cdot r_2$ |
275 sense? The $\cdot$-case is more complicated: if $r_1\cdot r_2$ |
276 matches a string of the form $c\!::\!s$, then the first part |
276 matches a string of the form $c\!::\!s$, then the first part |
277 must be matched by $r_1$. Consequently, it makes sense to |
277 must be matched by $r_1$. Consequently, it makes sense to |
278 construct the regular expression for $s$ by calling $der$ with |
278 construct the regular expression for $s$ by calling $der$ with |
279 $r_1$ and ``appending'' $r_2$. There is however one exception |
279 $r_1$ and ``appending'' $r_2$. There is however one exception |
330 Step 2: & build derivative of $b$ and $r_2$ & $(r_3 = der\,b\,r_2)$\smallskip\\ |
330 Step 2: & build derivative of $b$ and $r_2$ & $(r_3 = der\,b\,r_2)$\smallskip\\ |
331 Step 3: & build derivative of $c$ and $r_3$ & $(r_4 = der\,b\,r_3)$\smallskip\\ |
331 Step 3: & build derivative of $c$ and $r_3$ & $(r_4 = der\,b\,r_3)$\smallskip\\ |
332 Step 4: & the string is exhausted; test & ($nullable(r_4)$)\\ |
332 Step 4: & the string is exhausted; test & ($nullable(r_4)$)\\ |
333 & whether $r_4$ can recognise the\\ |
333 & whether $r_4$ can recognise the\\ |
334 & empty string\smallskip\\ |
334 & empty string\smallskip\\ |
335 Output: & result of the test $\Rightarrow true \,\text{or}\, \textit{false}$\\ |
335 Output: & result of this test $\Rightarrow true \,\text{or}\, \textit{false}$\\ |
336 \end{tabular} |
336 \end{tabular} |
337 \end{center} |
337 \end{center} |
338 |
338 |
339 \noindent Again the operation $Der$ might help to rationalise |
339 \noindent Again the operation $Der$ might help to rationalise |
340 this algorithm. We want to know whether $abc \in L(r_1)$. We |
340 this algorithm. We want to know whether $abc \in L(r_1)$. We |