\documentclass{article}

\usepackage{../style}

\usepackage{../graphics}

\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: