
diff -r 0b5f06539a84 -r dc5ab66b11cc hws/hw03.tex
--- a/hws/hw03.tex	Mon Oct 02 23:10:56 2023 +0100
+++ b/hws/hw03.tex	Tue Oct 03 14:29:12 2023 +0100
@@ -69,8 +69,13 @@
 
   What is the language recognised by this automaton?
 
+  
+
 \item Give a non-deterministic finite automaton that can
-      recognise the language $L(a\cdot (a + b)^* \cdot c)$.
+  recognise the language $L(a\cdot (a + b)^* \cdot c)$.
+
+  \solution{It is already possible to just read off the automaton without
+  going through Thompson.}
 
 \item Given a deterministic finite automaton $A(\varSigma, Q, Q_0, F,
       \delta)$, define which language is recognised by this
@@ -232,7 +237,7 @@
   automaton (DFA) that can recognise the same language
   as the NFA maximal need?
 
-  \solution{ $2^n$ in the worst-case and for some regexes the worst case
+  \solution{$2^n$ in the worst-case and for some regexes the worst case
     cannot be avoided. 
 
     Other comments: $r^{\{n\}}$ can only be represented as $n$
@@ -241,6 +246,16 @@
     represented as automaton.
   }
 
+\item Rust implements a non-backtracking regular expression matcher
+  based on the classic idea of DFAs. Still, some regular expressions
+  take a surprising amount of time for matching problems. Explain the
+  problem?
+
+  \solution{The problem has to do with bounded regular expressions,
+    such as $r^{\{n\}}$. They are represented as $n$-copies of some
+    automaton for $r$. If $n$ is large, then this can result in a
+    large memory-footprint and slow runtime.}
+
 \item Prove that for all regular expressions $r$ we have
       
 \begin{center} 




