--- 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}