1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 \usepackage{tikz}

     7 \usetikzlibrary{automata}

     8 

     9 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    10 

    11 \begin{document}

    12 

    13 \section*{Homework 9}

    14 

    15 \begin{enumerate}

    16 \item Describe what is meant by \emph{eliminating tail recursion}, when such an 

    17 optimization can be applied and why it is a benefit?

    18 

    19 \item It is true (I confirmed it) that

    20 

    21 \begin{center}

    22 if $\varnothing$ does not occur in $r$ \;\;then\;\;$L(r) \not= \{\}$

    23 \end{center}

    24 

    25 \noindent

    26 holds, or equivalently

    27 

    28 \begin{center}

    29 $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.

    30 \end{center}

    31 

    32 \noindent

    33 You can prove either version by induction on $r$. The best way to

    34 make more formal what is meant by `$\varnothing$ occurs in $r$', you can define

    35 the following function:

    36 

    37 \begin{center}

    38 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

    39 $occurs(\varnothing)$      & $\dn$ & $true$\\

    40 $occurs(\epsilon)$           & $\dn$ &  $f\!alse$\\

    41 $occurs (c)$                    & $\dn$ &  $f\!alse$\\

    42 $occurs (r_1 + r_2)$       & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\ 

    43 $occurs (r_1 \cdot r_2)$ & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\

    44 $occurs (r^*)$                & $\dn$ & $occurs(r)$ \\

    45 \end{tabular}

    46 \end{center}

    47 

    48 \noindent

    49 Now you can prove 

    50 

    51 \begin{center}

    52 $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.

    53 \end{center}

    54 

    55 \noindent

    56 The interesting cases are $r_1 + r_2$ and $r^*$.

    57 The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example

    58 is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding

    59 language is not empty. The obvious extension to include the not-regular expression, $\sim r$,

    60 also leads to an incorrect statement. Suppose we add the clause

    61   

    62 \begin{center}

    63 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

    64 $occurs(\sim r)$      & $\dn$ & $occurs(r)$

    65 \end{tabular}

    66 \end{center}  

    67 

    68 \noindent

    69 to the definition above, then it will not be true that

    70 

    71 \begin{center}

    72 $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.

    73 \end{center}

    74 

    75 \noindent

    76 Assume the alphabet contains just $a$ and $b$, find a counter example to this

    77 property.

    78   

    79 \end{enumerate}

    80 

    81 \end{document}

    82 

    83 %%% Local Variables: 

    84 %%% mode: latex

    85 %%% TeX-master: t

    86 %%% End: