53 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} |
53 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} |
54 $L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ |
54 $L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ |
55 $L(r^+)$ & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\ |
55 $L(r^+)$ & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\ |
56 $L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ |
56 $L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ |
57 $L(r^{\{n,m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\ |
57 $L(r^{\{n,m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\ |
58 $L(\sim{}r)$ & $\dn$ & $\mathbb{A} - L(r)$ |
58 $L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ |
59 \end{tabular} |
59 \end{tabular} |
60 \end{center} |
60 \end{center} |
61 |
61 |
62 \noindent |
62 \noindent |
63 whereby in the last clause the set $\mathbb{A}$ stands for the set of |
63 whereby in the last clause the set $\Sigma^*$ stands for the set of |
64 \emph{all} strings. So $\sim{}r$ means `all the strings that $r$ |
64 \emph{all} strings over the alphabet $\Sigma$ (in the implementation the |
|
65 alphabet can be just what is represented by, say, the type \pcode{char})). |
|
66 So $\sim{}r$ means `all the strings that $r$ |
65 cannot match'. |
67 cannot match'. |
66 |
68 |
67 Be careful that your implementation of $nullable$ and $der$ satisfies |
69 Be careful that your implementation of $nullable$ and $der$ satisfies |
68 for every $r$ the following two properties (see also Question 2): |
70 for every $r$ the following two properties (see also Question 2): |
69 |
71 |
106 $der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\ |
108 $der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\ |
107 $der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ |
109 $der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ |
108 \end{tabular} |
110 \end{tabular} |
109 \end{center} |
111 \end{center} |
110 |
112 |
|
113 \noindent |
|
114 Remember your definitions have to satisfy the two properties |
|
115 |
|
116 \begin{itemize} |
|
117 \item $nullable(r)$ if and only if $[]\in L(r)$ |
|
118 \item $L(der\,c\,r)) = Der\,c\,(L(r))$ |
|
119 \end{itemize} |
|
120 |
111 \subsection*{Question 3 (marked with 1\%)} |
121 \subsection*{Question 3 (marked with 1\%)} |
112 |
122 |
113 Implement the following regular expression for email addresses |
123 Implement the following regular expression for email addresses |
114 |
124 |
115 \[ |
125 \[ |
128 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\ |
138 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\ |
129 $r \cdot \epsilon$ & $\mapsto$ & $r$\\ |
139 $r \cdot \epsilon$ & $\mapsto$ & $r$\\ |
130 $\epsilon \cdot r$ & $\mapsto$ & $r$\\ |
140 $\epsilon \cdot r$ & $\mapsto$ & $r$\\ |
131 $r + \varnothing$ & $\mapsto$ & $r$\\ |
141 $r + \varnothing$ & $\mapsto$ & $r$\\ |
132 $\varnothing + r$ & $\mapsto$ & $r$\\ |
142 $\varnothing + r$ & $\mapsto$ & $r$\\ |
133 $r + r$ & $\mapsto$ & $r$ & (added on 12 October)\\ |
143 $r + r$ & $\mapsto$ & $r$\\ |
134 \end{tabular} |
144 \end{tabular} |
135 \end{center} |
145 \end{center} |
136 |
146 |
137 \noindent |
147 \noindent |
138 Write down your simplified derivative in the ``mathematicical'' |
148 Write down your simplified derivative in the ``mathematicical'' |