122 \item Recall the functions \textit{nullable} and \textit{zeroable}.

   122 \item Recall the functions \textit{nullable} and

   123   Define recursive functions \textit{atmostempty} (for regular expressions

   123       \textit{zeroable}.  Define recursive functions

   124   that match no string or only the empty string), \textit{somechars} (for regular

   124       \textit{atmostempty} (for regular expressions that match no

   125   expressions that match some non-empty string), \textit{infinitestrings} (for regular

   125       string or only the empty string), \textit{somechars} (for

   126   expressions that can match infinitely many strings). 

   126       regular expressions that match some non-empty string),

   127       \textit{infinitestrings} (for regular expressions that can match

   128       infinitely many strings).

   128   

   130 \item There are two kinds of automata that are generate for 

   131   regular expression matching---DFAs and NFAs. (1) Regular expression engines like

   132   the one in Python generate NFAs.  Explain what is the problem with such

   133   NFAs and what is the reason why they use NFAs. (2) Regular expression

   134   engines like the one in Rust generate DFAs. Explain what is the

   135   problem with these regex engines and also what is the problem with $a^{\{1000\}}$

   136   in these engines.

   137