259 It marks a part of a regular expression and can be used to extract the part of the |
259 It marks a part of a regular expression and can be used to extract the part of the |
260 string that is matched by this marked part of the regular expression. |
260 string that is matched by this marked part of the regular expression. |
261 } |
261 } |
262 |
262 |
263 \item Recall the functions \textit{nullable} and |
263 \item Recall the functions \textit{nullable} and |
264 \textit{zeroable}. Define recursive functions |
264 \textit{zeroable} from HW2. Define the cases of these |
|
265 functions for the $r^{\{n\}}$ regular expression. Recall that the first |
|
266 function needs to satisfy the property $\textit{nullable}(r)$ iff $[]\in L(r)$ and |
|
267 the second $\textit{zeroable}(r)$ iff $L(r) = \emptyset$ |
|
268 |
|
269 \solution{ |
|
270 $\textit{nullable}(r^{\{n\}}) \dn if n = 0 then true else \textit{nullable}(r)$ |
|
271 |
|
272 $\textit{zeroable}(r^{\{n\}}) \dn if n = 0 then false else \textit{zeroable}(r)$ |
|
273 } |
|
274 |
|
275 \item Define recursive functions |
265 \textit{atmostempty} (for regular expressions that match no |
276 \textit{atmostempty} (for regular expressions that match no |
266 string or only the empty string), \textit{somechars} (for |
277 string or only the empty string), \textit{somechars} (for |
267 regular expressions that match some non-empty string), |
278 regular expressions that match some non-empty string), |
268 \textit{infinitestrings} (for regular expressions that can match |
279 \textit{infinitestrings} (for regular expressions that can match |
269 infinitely many strings). |
280 infinitely many strings). |