diff -r ef54868a9226 -r 2f3c077359c4 hws/hw02.tex
--- a/hws/hw02.tex	Sat Sep 23 23:53:06 2023 +0100
+++ b/hws/hw02.tex	Mon Sep 25 13:14:34 2023 +0100
@@ -39,9 +39,10 @@
       explanation; otherwise give a counter-example.
 
       \solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where
-        $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$\medskip
+        $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$ is an
+        counter-example.\medskip
 
-        For equations like 3 it is always a god idea to prove the
+        For equations like 3 it is always a good idea to prove the
         two inclusions
 
         \[
@@ -67,7 +68,7 @@
         if $s_2 \in A^*$ then there exists an $m$ such that $s_2 \in A^m$.\bigskip
 
 
-        Aside: We are going to show that
+        Aside: We are going to show the following power law
 
         \[
         A^n \,@\, A^m = A^{n+m}  
@@ -127,20 +128,66 @@
 
       \solution{Both are equivalent, but why the second? Essentially you have to show that each string in one set is in the other. For 2 this means you can do an induction proof that $(ab)^na$ is the same string as $a(ba)^n$, where the former is in the first set and the latter in the second.}
 
-\item Given the regular expression $r = (a \cdot b + b)^*$.
-      Compute what the derivative of $r$ is with respect to
-      $a$, $b$ and $c$. Is $r$ nullable?
 
 \item Give an argument for why the following holds:
   if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$.
 
-  \solution{This was from last week; I just explicitly added it here.}
+  \solution{ This requires an inductive proof. There are a number of
+    ways to prove this. It is clear that if $s \in L (r^{\{n\}})$ then
+    also $s \in L (r^{\{..n\}})$.
+
+    So one way to prove this is to show
+    that if $s \in L (r^{\{..n\}})$ then also $s \in L (r^{\{n\}})$
+    (under the assumption that $r$ is nullable, otherwise it would not
+    be true).  The assumption $s \in L (r^{\{..n\}})$ means
+    that $s \in L(r^{\{i\}})$ with $i \leq n$ holds
+    and we have to show that $s \in L(r^{\{n\}})$ holds. 
+
+    One can do this by induction for languages as follows:
+
+    \[
+      \textit{if}\; [] \in A \;\textit{and}\; s \in A^n
+      \;\textit{then}\; s \in A^{n+m}
+    \]  
+
+    The proof is by induction on $m$. The base case $m=0$ is trivial.
+    For the $m + 1$ case we have the induction hypothesis:
+
+    \[
+      \textit{if}\; [] \in A \;\textit{and}\; s \in A^n
+      \;\textit{then}\; s \in A^{n+m}  
+    \]  
+
+    and we have to show
+
+    \[
+    s \in A^{n+m+1}   
+    \]  
+
+    under the assumption $[] \in A$ and $s \in A^n$. From the
+    assumptions and the IH we can infer that $s\in A^{n + m}$.
+    Then using the assumption $[] \in A$ we can infer that also
+
+    \[
+      s\in A \,@\, A^{n + m}
+    \]
+
+    which is equivalent to what we need to show $s \in A^{n+m+1}$.
+
+    Now we know $s \in L(r^{\{i\}})$ with $i \leq n$. Since $i + m = n$
+    for some $m$ we can conclude that $s \in L(r^{\{n\}})$. Done.
+    
+  }
+
+\item Given the regular expression $r = (a \cdot b + b)^*$.
+      Compute what the derivative of $r$ is with respect to
+      $a$, $b$ and $c$. Is $r$ nullable?
   
 \item Define what is meant by the derivative of a regular
       expressions with respect to a character. (Hint: The
       derivative is defined recursively.)
 
-      \solution{the recursive function for $der$}
+      \solution{The recursive function for $der$.}
       
 \item  Assume the set $Der$ is defined as
 
@@ -235,7 +282,7 @@
 
     (copied from somewhere ;o)
 
-    The idea behind it is essentially the DFA
+    The idea behind this monstrous regex is essentially the DFA
 
 \begin{center}    
 \begin{tikzpicture}[scale=1,>=stealth',very thick,
@@ -256,6 +303,10 @@
             (q3) edge[bend left] node[left]  {$b$} (q1);
 \end{tikzpicture}
 \end{center}
+
+  Maybe a good idea to reconsider this example in Lecture 3
+  where the Brzozowski algorithm for DFA $\rightarrow$ Regex
+  can be used.
 }
 
 \item \POSTSCRIPT