\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}\noindentholds, or equivalently\begin{center}$L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.\end{center}\noindentYou can prove either version by induction on $r$. The best way tomake more formal what is meant by `$\varnothing$ occurs in $r$', you can definethe 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}\noindentNow you can prove \begin{center}$L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.\end{center}\noindentThe 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 exampleis $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the correspondinglanguage 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} \noindentto the definition above, then it will not be true that\begin{center}$L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.\end{center}\noindentAssume the alphabet contains just $a$ and $b$, find a counter example to thisproperty.\end{enumerate}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: