diff -r 4189cb63e5db -r ce5de01b9632 hws/hw01.tex
--- a/hws/hw01.tex	Mon Sep 30 10:47:49 2024 +0100
+++ b/hws/hw01.tex	Fri Oct 11 19:13:00 2024 +0100
@@ -121,7 +121,26 @@
       $[b]$.
 
       \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$.
-        Can students think about why this is the case? - this would need a proof.}
+        Can students think about why this is the case? - this would need a proof.\bigskip
+
+
+        Lemma to prove: $A^* = \{[]\} \cup A \times A^*$ for any language $A$.\bigskip
+
+        The definition of ${}^*$: $\bigcup n. A^n$\bigskip
+
+        We first show $\subseteq$ of the lemma: a string $s \in A^*$, must also be in
+        $\bigcup n. A^n$, which means there is an $n$ such that $s\in A^n$.
+        If $n = 0$ then $s = []$ and $s$ is also in $\{[]\} \cup A \times A^*$.
+        If $n$ is bigger than $0$, then $s\in A^n$, which means by
+        definition of power that $s\in A \times A^{n - 1}$. But then
+        also $s \in A \times A^*$. That is one direction.\bigskip
+
+        The other direction: Two cases: (i) $s\in \{[]\}$ then
+        also $s\in A^*$. (ii) $s\in A \times A^*$ means there exists
+        an $n$ such that $s\in A\times A^n$. This in turn means
+        $s\in A^{n + 1}$ (by definition of power). But this also means $s\in A^*$.
+        So $\{[]\} \cup A \times A^*$ is a subset of $A^*$. Done!
+      }
 
 \item What is meant by the notions \emph{evil regular expressions}
   and by \emph{catastrophic backtracking}?