--- 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),