diff -r f824e1331fc6 -r bd5a8a6b3871 hws/hw09.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hws/hw09.tex	Wed Nov 27 21:36:30 2013 +0000
@@ -0,0 +1,86 @@
+\documentclass{article}
+\usepackage{charter}
+\usepackage{hyperref}
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage{tikz}
+\usetikzlibrary{automata}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
+\begin{document}
+
+\section*{Homework 9}
+
+\begin{enumerate}
+\item Describe what is meant by \emph{eliminating tail 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.
+  
+\end{enumerate}
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: