
diff -r 4a15a336022c -r 908e4f6cdf7c hws/hw04.tex
--- a/hws/hw04.tex	Fri Oct 21 13:30:12 2022 +0100
+++ b/hws/hw04.tex	Fri Oct 28 09:08:13 2022 +0100
@@ -2,6 +2,16 @@
 \usepackage{../style}
 \usepackage{../graphics}
 
+\newcommand{\solution}[1]{%
+  \begin{quote}\sf%
+    #1%
+  \end{quote}}
+\renewcommand{\solution}[1]{}
+
+
+
+
+
 \begin{document}
 
 \section*{Homework 4}
@@ -25,7 +35,42 @@
   
 
 \item If a regular expression $r$ does not contain any occurrence of $\ZERO$,  
-is it possible for $L(r)$ to be empty? Explain why, or give a proof.
+  is it possible for $L(r)$ to be empty? Explain why, or give a proof.
+
+  \solution{
+    The property to prove is
+
+    \begin{center}
+    $P(r)$: If $r$ does not contain $\ZERO$, then $L(r) \not= \emptyset$.  
+  \end{center}
+
+  For this you have to now go through all cases.
+
+  Case $r = 0$: $P(\ZERO)$ says: If $\ZERO$ does not contain $\ZERO$
+  then \ldots. The premise is obviously false, so everything follows,
+  in particular $L(r) \not= \emptyset$.\medskip
+
+  Case $r = \ONE$ and $r = c$ are similar, just that the premise is
+  true, but also $L(\ONE)$ and $L(c)$ are not empty. So we shown
+  $L(r) \not= \emptyset$.\medskip
+
+  Case $r = r_1 + r_2$: We know $P(r_1)$ and $P(r_2)$ as IHs. We need to show
+  $P(r_1 + r_2)$: If $r_1 + r_2$ does not contain $\ZERO$, then $L(r_1 + r_2) \not= \emptyset$.
+
+  If $r_1 + r_2$ does not contain $\ZERO$, then also $r_1$ does not contain $\ZERO$
+  and $r_2$ does not contain $\ZERO$. So we can apply the two IHs $P(r_1)$ and $P(r_2)$,
+  which allow us to infer that $L(r_1) \not= \emptyset$ and $L(r_2) \not= \emptyset$.
+  But if this is the case, then also $L(r_1 + r_2) \not= \emptyset$, which is what we needed
+  to show in this case.\medskip
+
+  The other cases are similar.\bigskip
+
+
+  This lemma essentially says that for basic regular expressions, if
+  they do not match anything at all, they must contain $\ZERO$(s)
+  somewhere.
+
+}
 
 \item Define the tokens and regular expressions for a language
   consisting of numbers, left-parenthesis $($, right-parenthesis $)$,
@@ -47,6 +92,19 @@
 
   holds.
 
+  \solution{
+    If $r$ is nullable, then $1 + r \equiv r$. With this you can replace
+
+    \begin{align}
+      (1 + r) + r\cdot r & \equiv  r + r\cdot r\\
+                         & \equiv  r \cdot (1 + r)\\
+                         & \equiv  r \cdot r
+    \end{align}  
+
+    where in (2) you pull out the ``factor'' $r$ (because $r_1 \cdot (r_2 + r_3) \equiv r_1 \cdot r_2 + r_1 \cdot r_3$).
+  }
+  
+
 \item \textbf{(Deleted)} Assume that $s^{-1}$ stands for the operation of reversing a
   string $s$. Given the following \emph{reversing} function on regular
   expressions
@@ -126,6 +184,66 @@
       regular expressions that match some non-empty string),
       \textit{infinitestrings} (for regular expressions that can match
       infinitely many strings).
+
+      \solution{
+        \textbf{zeroable}: The property is $z(r) \;\text{iff}\; L(r) = \emptyset$:
+
+        \begin{align}
+          z(\ZERO) &\dn true\\
+          z(\ONE)  &\dn false\\
+          z(c)     &\dn false\\
+          z(r_1 + r_2) &\dn z(r_1) \wedge z(r_2)\\
+          z(r_1 \cdot r_2) &\dn z(r_1) \vee z(r_2)\\
+          z(r^*)  &\dn false
+        \end{align}\bigskip
+
+        \textbf{atmostempty}: The property is ``either $L(r) = \emptyset$ or $L(r) = \{[]\}$'', which
+        is more formally $a(r) \;\text{iff}\; L(r) \subseteq \{[]\}$:
+
+        \begin{align}
+          a(\ZERO) &\dn true\\
+          a(\ONE)  &\dn true\\
+          a(c)     &\dn false\\
+          a(r_1 + r_2) &\dn a(r_1) \wedge a(r_2)\\
+          a(r_1 \cdot r_2) &\dn z(r_1) \vee z(r_2) \vee (a(r_1) \wedge a(r_2))\\
+          a(r^*)  &\dn a(r)
+        \end{align}
+
+        For this it is good to remember the regex should either not
+        match anything at all, or just the empty string.\bigskip
+
+        \textbf{somechars}: The property is ``$L(r)$ must contain a string which is not the empty string'', which
+        is more formally $s(r) \;\text{iff}\; \exists\,s. s \not= [] \wedge s \in L(r)$:
+
+        \begin{align}
+          s(\ZERO) &\dn false\\
+          s(\ONE)  &\dn false\\
+          s(c)     &\dn true\\
+          s(r_1 + r_2) &\dn s(r_1) \vee s(r_2)\\
+          s(r_1 \cdot r_2) &\dn (\neg z(r_1) \wedge s(r_2)) \;\vee\; (\neg z(r_2) \wedge s(r_1))\\
+          s(r^*)  &\dn s(r)
+        \end{align}
+
+        Here the interesting case is $r_1 \cdot r_2$ where one essentially has to make sure
+        that one of the regexes is not zeroable, because then the resulting regex cannot match any
+        string.\bigskip
+
+        \textbf{infinitestrings}: The property is
+        $i(r) \;\text{iff}\; L(r)\;\text{is infinite}$:
+
+        \begin{align}
+          i(\ZERO) &\dn false\\
+          i(\ONE)  &\dn false\\
+          i(c)     &\dn false\\
+          i(r_1 + r_2) &\dn i(r_1) \vee i(r_2)\\
+          i(r_1 \cdot r_2) &\dn (\neg z(r_1) \wedge i(r_2)) \;\vee\; (\neg z(r_2) \wedge i(r_1))\\
+          i(r^*)  &\dn \neg a(r)
+        \end{align}
+
+        Here the interesting bit is that as soon $r$ can match at least a single string, then $r^*$
+        will match infinitely many strings.
+        }
+
       
 \item There are two kinds of automata that are generated for 
   regular expression matching---DFAs and NFAs. (1) Regular expression engines like




