# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1759837640 -3600
# Node ID 18b411abd3071737e9e53cd7bae8a89f2c9eb25d
# Parent  ff0c787f7c7cb6e0cddb647308816259936f6dee
updated

diff -r ff0c787f7c7c -r 18b411abd307 hws/hw03.pdf
Binary file hws/hw03.pdf has changed
diff -r ff0c787f7c7c -r 18b411abd307 hws/hw03.tex
--- a/hws/hw03.tex	Sat Oct 04 22:28:07 2025 +0100
+++ b/hws/hw03.tex	Tue Oct 07 12:47:20 2025 +0100
@@ -190,34 +190,34 @@
         (Q2,a)->Q2 (Q2,b)->Q0.
         }
   
-\item %%\textbf{(Deleted for 2017, 2018, 2019)}
-  Given the following deterministic finite automaton over the
-  alphabet $\{0, 1\}$, find the corresponding minimal automaton. In
-  case states can be merged, state clearly which states can be merged.
+%\item %%\textbf{(Deleted for 2017, 2018, 2019)}
+%  Given the following deterministic finite automaton over the
+%  alphabet $\{0, 1\}$, find the corresponding minimal automaton. In
+%  case states can be merged, state clearly which states can be merged.
+%
+%  \begin{center}
+%    \begin{tikzpicture}[>=stealth',very thick,auto,
+%                        every state/.style={minimum size=0pt,
+%                        inner sep=2pt,draw=blue!50,very thick,
+%                        fill=blue!20},scale=2]
+%      \node[state, initial]        (q0) at ( 0,1) {$Q_0$};
+%      \node[state]                    (q1) at ( 1,1) {$Q_1$};
+%      \node[state, accepting] (q4) at ( 2,1) {$Q_4$};
+%      \node[state]                    (q2) at (0.5,0) {$Q_2$};
+%      \node[state]                    (q3) at (1.5,0) {$Q_3$};
+%      \path[->] (q0) edge node[above] {$0$} (q1)
+%                (q0) edge node[right] {$1$} (q2)
+%                (q1) edge node[above] {$0$} (q4)
+%                (q1) edge node[right] {$1$} (q2)
+%                (q2) edge node[above] {$0$} (q3)
+%                (q2) edge [loop below] node {$1$} ()
+%                (q3) edge node[left] {$0$} (q4)
+%                (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
+%                (q4) edge [loop right] node {$0, 1$} ();
+%    \end{tikzpicture}
+%  \end{center}
 
-  \begin{center}
-    \begin{tikzpicture}[>=stealth',very thick,auto,
-                        every state/.style={minimum size=0pt,
-                        inner sep=2pt,draw=blue!50,very thick,
-                        fill=blue!20},scale=2]
-      \node[state, initial]        (q0) at ( 0,1) {$Q_0$};
-      \node[state]                    (q1) at ( 1,1) {$Q_1$};
-      \node[state, accepting] (q4) at ( 2,1) {$Q_4$};
-      \node[state]                    (q2) at (0.5,0) {$Q_2$};
-      \node[state]                    (q3) at (1.5,0) {$Q_3$};
-      \path[->] (q0) edge node[above] {$0$} (q1)
-                (q0) edge node[right] {$1$} (q2)
-                (q1) edge node[above] {$0$} (q4)
-                (q1) edge node[right] {$1$} (q2)
-                (q2) edge node[above] {$0$} (q3)
-                (q2) edge [loop below] node {$1$} ()
-                (q3) edge node[left] {$0$} (q4)
-                (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
-                (q4) edge [loop right] node {$0, 1$} ();
-    \end{tikzpicture}
-  \end{center}
-
-  \solution{Q0 and Q2 can be merged; and Q1 and Q3 as well}
+%  \solution{Q0 and Q2 can be merged; and Q1 and Q3 as well}
 
 \item Given the following finite deterministic automaton over the alphabet $\{a, b\}$:
 
@@ -272,6 +272,33 @@
     automaton for $r$. If $n$ is large, then this can result in a
     large memory-footprint and slow runtime.}
 
+\item On Mentimeter there was a question: \textit{``Why does the [regex] $(a^*)^*b$ takes much longer for 
+strings of length 28 compared to say 25?''}\smallskip\\
+
+For this consider a lake with $1000 m^3$ surface and an invasive plant
+that tries to cover the lake with leaves, think of the famous  water lily that
+produces leaves on which you can stand. This plant starts out with a
+seedling covering just $0.001 m^3$ of the lake, but doubles every day
+the surface that is covers. So on day two it would cover $0.002 m^3$,
+on day three $0.004 m^3$ and so on. How many days does the plant need to 
+cover the entire lake? How many days is the lake still 90\% \emph{un}covered? 
+
+\solution{That is a classic example of the law of exponentiation, meaning an 
+ exponential function grows very slowly at first, but then explodes. It should take
+20 days to completely cover the lake: $0.001 * 2^{20}$. But up to day 16 still less
+than 10\% are covered. The remaining 90\% covering comes essentially in the last 3 
+days only. That is the same with any exponential algorithm: they are pretty ok for some 
+small values, but then they suddenly explode where they are not ok anymore.\\
+
+PS: After COVID, we should all be more aware of the incredible growth of
+exponential functions. That is why I liked that Ms~Merkel was in
+charge of Germany during COVID and managed to keep numbers of dead
+people in Germany relatively low...not all was smooth of course. But she 
+was a scientist in her former life (actually a physicist) and knew about
+exponential growth. While we over here had this clown Boris Johnson in charge, 
+who with  his joke-education and smashing up restaurants, had no clue what an
+exponential function is.}
+
 \item Prove that for all regular expressions $r$ we have
       
 \begin{center}