66 |
66 |
67 where the three dots stand for arbitrary characters, but not comment delimiters. |
67 where the three dots stand for arbitrary characters, but not comment delimiters. |
68 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
68 (Hint: You can assume you are already given a regular expression written \texttt{ALL}, |
69 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
69 that can recognise any character, and a regular expression \texttt{NOT} that recognises |
70 the complement of a regular expression.) |
70 the complement of a regular expression.) |
|
71 |
|
72 \item Simplify the regular expression |
71 |
73 |
72 \item How many basic regular expressions are there to match the string |
74 \[ |
73 $abcd$? (ii) How many if they cannot include $\epsilon$ and |
75 (\varnothing \cdot (b \cdot c)) + |
74 $\varnothing$? (iii) How many if they are also not allowed to |
76 ((\varnothing \cdot c) + \epsilon) |
75 contain stars? (iv) How many if they are also not allowed to contain |
77 \] |
76 $\_ + \_$? |
|
77 |
78 |
|
79 Does simplification always preserve the meaning of a regular |
|
80 expression? |
|
81 |
|
82 \item The Sulzmann algorithm contains the function $mkeps$ |
|
83 which answers how a regular expression can match the |
|
84 empty string. What is the answer of $mkeps$ for the |
|
85 regular expressions: |
|
86 |
|
87 \[ |
|
88 \begin{array}{l} |
|
89 (\varnothing \cdot (b \cdot c)) + |
|
90 ((\varnothing \cdot c) + \epsilon)\\ |
|
91 (a + \varepsilon) \cdot (\varepsilon + \varepsilon) |
|
92 \end{array} |
|
93 \] |
|
94 |
|
95 \item What is the purpose of the record regular expression |
|
96 in the Sulzmann algorithm? |
|
97 |
|
98 |
78 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
99 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as |
79 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
100 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so |
80 %that it filters out all comments and whitespace from the result. |
101 %that it filters out all comments and whitespace from the result. |
81 |
102 |
82 %\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it |
103 %\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it |