9 \begin{enumerate} |
9 \begin{enumerate} |
10 \item Describe what is meant by \emph{eliminating tail |
10 \item Describe what is meant by \emph{eliminating tail |
11 recursion}, when such an optimization can be applied and |
11 recursion}, when such an optimization can be applied and |
12 why it is a benefit? |
12 why it is a benefit? |
13 |
13 |
14 \item It is true (I confirmed it) that |
14 % \item It is true (I confirmed it) that |
15 |
15 % |
16 \begin{center} if $\varnothing$ does not occur in $r$ |
16 % \begin{center} if $\varnothing$ does not occur in $r$ |
17 \;\;then\;\;$L(r) \not= \{\}$ |
17 % \;\;then\;\;$L(r) \not= \{\}$ |
18 \end{center} |
18 % \end{center} |
19 |
19 % |
20 \noindent |
20 % \noindent |
21 holds, or equivalently |
21 % holds, or equivalently |
22 |
22 % |
23 \begin{center} |
23 % \begin{center} |
24 $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$. |
24 % $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$. |
25 \end{center} |
25 % \end{center} |
26 |
26 % |
27 \noindent |
27 % \noindent |
28 You can prove either version by induction on $r$. The best way to |
28 % You can prove either version by induction on $r$. The best way to |
29 make more formal what is meant by `$\varnothing$ occurs in $r$', you can define |
29 % make more formal what is meant by `$\varnothing$ occurs in $r$', you can define |
30 the following function: |
30 % the following function: |
31 |
31 % |
32 \begin{center} |
32 % \begin{center} |
33 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
33 % \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
34 $occurs(\varnothing)$ & $\dn$ & $true$\\ |
34 % $occurs(\varnothing)$ & $\dn$ & $true$\\ |
35 $occurs(\epsilon)$ & $\dn$ & $f\!alse$\\ |
35 % $occurs(\epsilon)$ & $\dn$ & $f\!alse$\\ |
36 $occurs (c)$ & $\dn$ & $f\!alse$\\ |
36 % $occurs (c)$ & $\dn$ & $f\!alse$\\ |
37 $occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ |
37 % $occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ |
38 $occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ |
38 % $occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ |
39 $occurs (r^*)$ & $\dn$ & $occurs(r)$ \\ |
39 % $occurs (r^*)$ & $\dn$ & $occurs(r)$ \\ |
40 \end{tabular} |
40 % \end{tabular} |
41 \end{center} |
41 % \end{center} |
42 |
42 % |
43 \noindent |
43 % \noindent |
44 Now you can prove |
44 % Now you can prove |
45 |
45 % |
46 \begin{center} |
46 % \begin{center} |
47 $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$. |
47 % $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$. |
48 \end{center} |
48 % \end{center} |
49 |
49 % |
50 \noindent |
50 % \noindent |
51 The interesting cases are $r_1 + r_2$ and $r^*$. |
51 % The interesting cases are $r_1 + r_2$ and $r^*$. |
52 The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example |
52 % The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example |
53 is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding |
53 % is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding |
54 language is not empty. The obvious extension to include the not-regular expression, $\sim r$, |
54 % language is not empty. The obvious extension to include the not-regular expression, $\sim r$, |
55 also leads to an incorrect statement. Suppose we add the clause |
55 % also leads to an incorrect statement. Suppose we add the clause |
56 |
56 % |
57 \begin{center} |
57 % \begin{center} |
58 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
58 % \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
59 $occurs(\sim r)$ & $\dn$ & $occurs(r)$ |
59 % $occurs(\sim r)$ & $\dn$ & $occurs(r)$ |
60 \end{tabular} |
60 % \end{tabular} |
61 \end{center} |
61 % \end{center} |
62 |
62 % |
63 \noindent |
63 % \noindent |
64 to the definition above, then it will not be true that |
64 % to the definition above, then it will not be true that |
65 |
65 % |
66 \begin{center} |
66 % \begin{center} |
67 $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$. |
67 % $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$. |
68 \end{center} |
68 % \end{center} |
69 |
69 % |
70 \noindent |
70 % \noindent |
71 Assume the alphabet contains just $a$ and $b$, find a counter example to this |
71 % Assume the alphabet contains just $a$ and $b$, find a counter example to this |
72 property. |
72 % property. |
73 |
73 |
74 \end{enumerate} |
74 \end{enumerate} |
75 |
75 |
76 \end{document} |
76 \end{document} |
77 |
77 |