diff -r 49d21814a633 -r 771396fa6cc4 hws/hw01.tex
--- a/hws/hw01.tex	Fri Sep 16 12:52:21 2022 +0100
+++ b/hws/hw01.tex	Thu Sep 29 20:54:02 2022 +0100
@@ -2,6 +2,11 @@
 \documentclass{article}
 \usepackage{../style}
 
+\newcommand{\solution}[1]{%
+  \begin{quote}\sf%
+    #1%
+  \end{quote}}
+
 \begin{document}
 
 \section*{Homework 1}
@@ -47,11 +52,21 @@
       strings and languages. In the context of the CFL-course,
       what is meant by the term \emph{language}?
 
+      \solution{A language - in this context - is just a set of
+        strings. Some of these sets can actually not be described by
+        regular expressions. Only regular​ languages can. This is
+        something for lecture 3.}
+      
 \item Give the definition for regular expressions---this is an
       inductive datatype. What is the
       meaning of a regular expression? (Hint: The meaning is
       defined recursively.)
 
+      \solution{Here I would also expect the grammar for basic regular
+        expressions and the definition of the recursive L-function. Discuss
+        differences between $r_1 + r_2$ and $r^+$. Discuss differences between
+      ``real-life regexes'' and regexes in this module.}
+
 \item Assume the concatenation operation of two strings is
       written as $s_1 @ s_2$. Define the operation of
       \emph{concatenating} two sets of strings. This operation
@@ -59,24 +74,38 @@
       this definition, what is $A \,@\, \{\}$ equal to?
       Is in general $A\,@\,B$ equal to $B\,@\,A$?
 
+      \solution{ What is $A @ {[]}$? Are there special cases
+      where $A @ B = B @ A$? }
+
 \item Assume a set $A$ contains 4 strings and a set $B$
       contains 7 strings. None of the strings is the empty
       string. How many strings are in $A \,@\, B$?
 
+      \solution{28, but there are corner cases where there are fewer
+        than 28 elements. Can students think of such corner cases?
+      For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ }
+
 \item How is the power of a language defined? (Hint: There are two
   rules, one for $\_^0$ and one for $\_^{n+1}$.)
 
+     \solution{Two rules: 0-case and n+1 case.}
+
 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
       are in $A^4$? (2) Consider also the case of $A^4$ where one of
       the strings in $A$ is the empty string, for example $A =
       \{[a], [b], [c], []\}$.
 
+      \solution{121 is correct. But make sure you understand why it is 121
+        in cases you do not have a computer at your fingertips.}
+
 \item (1) How many basic regular expressions are there to match
       \textbf{only} the string $abcd$? (2) How many if they cannot include
       $\ONE$ and $\ZERO$? (3) How many if they are also not
       allowed to contain stars? (4) How many if they are also
       not allowed to contain $\_ + \_$?
 
+      \solution{1-3 are infinite (tell the idea why - examples); 4 is five - remember regexes are trees.}
+      
 \item When are two regular expressions equivalent? Can you
       think of instances where two regular expressions match
       the same strings, but it is not so obvious that they do?
@@ -84,9 +113,14 @@
       obviously match the same strings, namely $[a]$ and
       $[b]$.
 
+      \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$.
+        Can students think about why this is the case?}
+
 \item What is meant by the notions \emph{evil regular expressions}
   and by \emph{catastrophic backtracking}?
 
+  \solution{catastrophic backtracking also applies to other regexes, not just $(a^*)^*b$}
+
 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$,
   which of the following regular expressions are equivalent
 
@@ -97,6 +131,8 @@
   3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$           % no
 \end{tabular}
 \end{center}
+
+  \solution{no, yes (why?), no.}
   
 
 \item \POSTSCRIPT