equal
deleted
inserted
replaced
226 \end{center} |
226 \end{center} |
227 |
227 |
228 \noindent |
228 \noindent |
229 In contrast to the function $nullable(r)$, which test whether a regular expression |
229 In contrast to the function $nullable(r)$, which test whether a regular expression |
230 can match the empty string, the $zeroable$ function identifies whether a regular |
230 can match the empty string, the $zeroable$ function identifies whether a regular |
231 expression cannot match anything at all. |
231 expression cannot match anything at all. The mathematical way of stating this |
232 |
232 is |
233 \begin{center} |
233 |
234 \texttt{\Grid{$c_1$\VS{} true\VS{} then\VS{} x\VS{} else\VS{} y \ldots }} |
234 \begin{center} |
235 \end{center} |
235 $s \in zeroable(s)$ implies $L(r) = \varnothing$ |
236 |
236 \end{center} |
237 \noindent |
237 |
238 The crucial idea of the algorithm is to build the derivative of all |
238 \noindent |
|
239 Let us fix a set of regular expressions $rs$. |
|
240 The crucial idea of the algorithm is to take the input string, say |
|
241 |
|
242 \begin{center} |
|
243 \texttt{\grid{$c_1$}\grid{$c_2$}\grid{$c_3$}\grid{$c_4$}\grid{\ldots}} |
|
244 \end{center} |
|
245 |
|
246 \noindent |
|
247 and build the derivative of all regular expressions in $rs$ with respect |
|
248 to the first character. Then we take the result and continue with $c_2$ |
|
249 until we have either exhausted our input string or all of the regula |
239 |
250 |
240 \end{document} |
251 \end{document} |
241 |
252 |
242 %%% Local Variables: |
253 %%% Local Variables: |
243 %%% mode: latex |
254 %%% mode: latex |