diff -r 432d027aa6f7 -r ae9ffbf979ff hws/hw04.tex --- a/hws/hw04.tex Sun Oct 12 12:50:16 2025 +0100 +++ b/hws/hw04.tex Fri Oct 17 11:20:49 2025 +0100 @@ -261,7 +261,18 @@ } \item Recall the functions \textit{nullable} and - \textit{zeroable}. Define recursive functions + \textit{zeroable} from HW2. Define the cases of these + functions for the $r^{\{n\}}$ regular expression. Recall that the first + function needs to satisfy the property $\textit{nullable}(r)$ iff $[]\in L(r)$ and + the second $\textit{zeroable}(r)$ iff $L(r) = \emptyset$ + + \solution{ + $\textit{nullable}(r^{\{n\}}) \dn if n = 0 then true else \textit{nullable}(r)$ + + $\textit{zeroable}(r^{\{n\}}) \dn if n = 0 then false else \textit{zeroable}(r)$ + } + +\item Define recursive functions \textit{atmostempty} (for regular expressions that match no string or only the empty string), \textit{somechars} (for regular expressions that match some non-empty string),