handouts/ho05.tex
changeset 158 77e8397ec2ec
parent 157 b6eee9571a63
child 159 ae5ceef5355e
equal deleted inserted replaced
157:b6eee9571a63 158:77e8397ec2ec
   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