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