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