Binary file hws/hw04.pdf has changed

--- a/hws/hw04.tex	Wed Oct 06 20:43:35 2021 +0100
+++ b/hws/hw04.tex	Sat Oct 09 12:29:15 2021 +0100
@@ -119,13 +119,22 @@
 \item What is the purpose of the record regular expression in
       the Sulzmann \& Lu algorithm?
 
-\item Recall the functions \textit{nullable} and \textit{zeroable}.
-  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), \textit{infinitestrings} (for regular
-  expressions that can match infinitely many strings). 
+\item Recall the functions \textit{nullable} and
+      \textit{zeroable}.  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),
+      \textit{infinitestrings} (for regular expressions that can match
+      infinitely many strings).
       
-  
+\item There are two kinds of automata that are generate for 
+  regular expression matching---DFAs and NFAs. (1) Regular expression engines like
+  the one in Python generate NFAs.  Explain what is the problem with such
+  NFAs and what is the reason why they use NFAs. (2) Regular expression
+  engines like the one in Rust generate DFAs. Explain what is the
+  problem with these regex engines and also what is the problem with $a^{\{1000\}}$
+  in these engines.
+      
 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so 
 %that it filters out all comments and whitespace from the result.