Binary file hws/hw02.pdf has changed

--- a/hws/hw02.tex	Mon Oct 10 12:42:06 2022 +0100
+++ b/hws/hw02.tex	Mon Oct 10 13:53:10 2022 +0100
@@ -1,6 +1,13 @@
 \documentclass{article}
 \usepackage{../style}
 
+\newcommand{\solution}[1]{%
+  \begin{quote}\sf%
+    #1%
+  \end{quote}}
+\renewcommand{\solution}[1]{}
+
+
 \begin{document}
 
 \section*{Homework 2}
@@ -9,10 +16,17 @@
 
 \begin{enumerate}
 \item What is the difference between \emph{basic} regular expressions  
-      and \emph{extended} regular expressions?
+  and \emph{extended} regular expressions?
+
+  \solution{Basic regular expressions are $\ZERO$, $\ONE$, $c$, $r_1 + r_2$,
+    $r_1 \cdot r_2$, $r^*$. The extended ones are the bounded
+    repetitions, not, etc.}
   
 \item What is the language recognised by the regular
-      expressions $(\ZERO^*)^*$.
+  expressions $(\ZERO^*)^*$.
+
+  \solution{$L(\ZERO^*{}^*) = \{[]\}$,
+    remember * always includes the empty string}
 
 \item Review the first handout about sets of strings and read
       the second handout. Assuming the alphabet is the set
@@ -30,31 +44,47 @@
       \noindent In case an equation is true, give an
       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], []\}$}
+
 \item Given the regular expressions $r_1 = \ONE$ and $r_2 =
       \ZERO$ and $r_3 = a$. How many strings can the regular
       expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
 
+      \solution{$r_1$ and $r_2$ can match the empty string only, $r_3$ can
+        match $[]$, $a$, $aa$, ....}
+
 \item Give regular expressions for (a) decimal numbers and for
       (b) binary numbers. Hint: Observe that the empty string
       is not a number. Also observe that leading 0s are
       normally not written---for example the JSON format for numbers
       explicitly forbids this.
 
+      \solution{Just numbers without leading 0s: $0 + (1..9)\cdot(0..1)^*$;
+        can be extended to decimal; similar for binary numbers
+      }
+
 \item Decide whether the following two regular expressions are
       equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot
       b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
 
+      \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\}}$.
+  if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$.
+
+  \solution{This was from last week; I just explicitly added it here.}
   
 \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$}
+      
 \item  Assume the set $Der$ is defined as
 
   \begin{center}
@@ -64,12 +94,18 @@
       What is the relation between $Der$ and the notion of
       derivative of regular expressions?
 
+      \solution{Main property is $L(der\,c\,r) = Der\,c\,(L(r))$.}
+
 \item Give a regular expression over the alphabet $\{a,b\}$
       recognising all strings that do not contain any
       substring $bb$ and end in $a$.
 
+      
+
 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) +
-      (b^*\cdot b^+)$ define the same language?
+  (b^*\cdot b^+)$ define the same language?
+
+   \solution{No, the first one can match for example abababababbbbb}
 
 \item Define the function $zeroable$ by recursion over regular
       expressions. This function should satisfy the property
@@ -96,7 +132,9 @@
 
 \item Give a regular expressions that can recognise all
       strings from the language $\{a^n\;|\;\exists k.\; n = 3 k
-      + 1 \}$. 
+      + 1 \}$.
+
+      \solution{$a(aaa)^*$}
       
 \item Give a regular expression that can recognise an odd 
 number of $a$s or an even number of $b$s.