# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1417182452 0
# Node ID 7dd5797a5ffa2958c0bb9bcb4995e7a9388576b2
# Parent  90ccc385c547860208fc6569fb86dac488cad818
updated

diff -r 90ccc385c547 -r 7dd5797a5ffa hws/hw09.pdf
Binary file hws/hw09.pdf has changed
diff -r 90ccc385c547 -r 7dd5797a5ffa hws/hw09.tex
--- a/hws/hw09.tex	Fri Nov 28 13:11:17 2014 +0000
+++ b/hws/hw09.tex	Fri Nov 28 13:47:32 2014 +0000
@@ -11,65 +11,65 @@
       recursion}, when such an optimization can be applied and
       why it is a benefit?
 
-\item It is true (I confirmed it) that
-
-\begin{center} if $\varnothing$ does not occur in $r$
-\;\;then\;\;$L(r) \not= \{\}$ 
-\end{center}
-
-\noindent
-holds, or equivalently
-
-\begin{center}
-$L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.
-\end{center}
-
-\noindent
-You can prove either version by induction on $r$. The best way to
-make more formal what is meant by `$\varnothing$ occurs in $r$', you can define
-the following function:
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-$occurs(\varnothing)$      & $\dn$ & $true$\\
-$occurs(\epsilon)$           & $\dn$ &  $f\!alse$\\
-$occurs (c)$                    & $\dn$ &  $f\!alse$\\
-$occurs (r_1 + r_2)$       & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\ 
-$occurs (r_1 \cdot r_2)$ & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\
-$occurs (r^*)$                & $\dn$ & $occurs(r)$ \\
-\end{tabular}
-\end{center}
-
-\noindent
-Now you can prove 
-
-\begin{center}
-$L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
-\end{center}
-
-\noindent
-The interesting cases are $r_1 + r_2$ and $r^*$.
-The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example
-is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding
-language is not empty. The obvious extension to include the not-regular expression, $\sim r$,
-also leads to an incorrect statement. Suppose we add the clause
-  
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-$occurs(\sim r)$      & $\dn$ & $occurs(r)$
-\end{tabular}
-\end{center}  
-
-\noindent
-to the definition above, then it will not be true that
-
-\begin{center}
-$L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
-\end{center}
-
-\noindent
-Assume the alphabet contains just $a$ and $b$, find a counter example to this
-property.
+%  \item It is true (I confirmed it) that
+%  
+%  \begin{center} if $\varnothing$ does not occur in $r$
+%  \;\;then\;\;$L(r) \not= \{\}$ 
+%  \end{center}
+%  
+%  \noindent
+%  holds, or equivalently
+%  
+%  \begin{center}
+%  $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.
+%  \end{center}
+%  
+%  \noindent
+%  You can prove either version by induction on $r$. The best way to
+%  make more formal what is meant by `$\varnothing$ occurs in $r$', you can define
+%  the following function:
+%  
+%  \begin{center}
+%  \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+%  $occurs(\varnothing)$      & $\dn$ & $true$\\
+%  $occurs(\epsilon)$           & $\dn$ &  $f\!alse$\\
+%  $occurs (c)$                    & $\dn$ &  $f\!alse$\\
+%  $occurs (r_1 + r_2)$       & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\ 
+%  $occurs (r_1 \cdot r_2)$ & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\
+%  $occurs (r^*)$                & $\dn$ & $occurs(r)$ \\
+%  \end{tabular}
+%  \end{center}
+%  
+%  \noindent
+%  Now you can prove 
+%  
+%  \begin{center}
+%  $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
+%  \end{center}
+%  
+%  \noindent
+%  The interesting cases are $r_1 + r_2$ and $r^*$.
+%  The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example
+%  is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding
+%  language is not empty. The obvious extension to include the not-regular expression, $\sim r$,
+%  also leads to an incorrect statement. Suppose we add the clause
+%    
+%  \begin{center}
+%  \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+%  $occurs(\sim r)$      & $\dn$ & $occurs(r)$
+%  \end{tabular}
+%  \end{center}  
+%  
+%  \noindent
+%  to the definition above, then it will not be true that
+%  
+%  \begin{center}
+%  $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
+%  \end{center}
+%  
+%  \noindent
+%  Assume the alphabet contains just $a$ and $b$, find a counter example to this
+%  property.
   
 \end{enumerate}