31 string $s$. Given the following \emph{reversing} function on regular |
31 string $s$. Given the following \emph{reversing} function on regular |
32 expressions |
32 expressions |
33 |
33 |
34 \begin{center} |
34 \begin{center} |
35 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
35 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
36 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
36 $rev(\ZERO)$ & $\dn$ & $\ZERO$\\ |
37 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
37 $rev(\ONE)$ & $\dn$ & $\ONE$\\ |
38 $rev(c)$ & $\dn$ & $c$\\ |
38 $rev(c)$ & $\dn$ & $c$\\ |
39 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
39 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
40 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
40 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
41 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
41 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
42 \end{tabular} |
42 \end{tabular} |
54 $L(rev(r)) = Rev (L(r))$ |
54 $L(rev(r)) = Rev (L(r))$ |
55 \end{center} |
55 \end{center} |
56 |
56 |
57 holds. |
57 holds. |
58 |
58 |
59 \item Assume the delimiters for comments are \texttt{$\slash$*} and |
59 \item Assume the delimiters for comments are |
60 \texttt{*$\slash$}. Give a regular expression that can recognise |
60 \texttt{$\slash$*} and \texttt{*$\slash$}. Give a |
61 comments of the form |
61 regular expression that can recognise comments of the |
|
62 form |
62 |
63 |
63 \begin{center} |
64 \begin{center} |
64 \texttt{$\slash$*~\ldots{}~*$\slash$} |
65 \texttt{$\slash$*~\ldots{}~*$\slash$} |
65 \end{center} |
66 \end{center} |
66 |
67 |
67 where the three dots stand for arbitrary characters, but not comment delimiters. |
68 where the three dots stand for arbitrary characters, but |
68 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
69 not comment delimiters. (Hint: You can assume you are |
69 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
70 already given a regular expression written \texttt{ALL}, |
70 the complement of a regular expression.) |
71 that can recognise any character, and a regular |
|
72 expression \texttt{NOT} that recognises the complement |
|
73 of a regular expression.) |
71 |
74 |
72 \item Simplify the regular expression |
75 \item Simplify the regular expression |
73 |
76 |
74 \[ |
77 \[ |
75 (\varnothing \cdot (b \cdot c)) + |
78 (\ZERO \cdot (b \cdot c)) + |
76 ((\varnothing \cdot c) + \epsilon) |
79 ((\ZERO \cdot c) + \ONE) |
77 \] |
80 \] |
78 |
81 |
79 Does simplification always preserve the meaning of a regular |
82 Does simplification always preserve the meaning of a |
80 expression? |
83 regular expression? |
81 |
84 |
82 \item The Sulzmann \& Lu algorithm contains the function $mkeps$ |
85 \item The Sulzmann \& Lu algorithm contains the function |
83 which answers how a regular expression can match the |
86 $mkeps$ which answers how a regular expression can match |
84 empty string. What is the answer of $mkeps$ for the |
87 the empty string. What is the answer of $mkeps$ for the |
85 regular expressions: |
88 regular expressions: |
86 |
89 |
87 \[ |
90 \[ |
88 \begin{array}{l} |
91 \begin{array}{l} |
89 (\varnothing \cdot (b \cdot c)) + |
92 (\ZERO \cdot (b \cdot c)) + |
90 ((\varnothing \cdot c) + \epsilon)\\ |
93 ((\ZERO \cdot c) + \ONE)\\ |
91 (a + \varepsilon) \cdot (\varepsilon + \varepsilon) |
94 (a + \ONE) \cdot (\ONE + \ONE) |
92 \end{array} |
95 \end{array} |
93 \] |
96 \] |
94 |
97 |
95 \item What is the purpose of the record regular expression |
98 \item What is the purpose of the record regular expression in |
96 in the Sulzmann \& Lu algorithm? |
99 the Sulzmann \& Lu algorithm? |
97 |
100 |
98 |
101 |
99 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
102 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
100 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
103 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
101 %that it filters out all comments and whitespace from the result. |
104 %that it filters out all comments and whitespace from the result. |