diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw01.tex --- a/coursework/cw01.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/coursework/cw01.tex Mon Sep 28 23:47:34 2015 +0100 @@ -55,13 +55,15 @@ $L(r^+)$ & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\ $L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ $L(r^{\{n,m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\ -$L(\sim{}r)$ & $\dn$ & $\mathbb{A} - L(r)$ +$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ \end{tabular} \end{center} \noindent -whereby in the last clause the set $\mathbb{A}$ stands for the set of -\emph{all} strings. So $\sim{}r$ means `all the strings that $r$ +whereby in the last clause the set $\Sigma^*$ stands for the set of +\emph{all} strings over the alphabet $\Sigma$ (in the implementation the +alphabet can be just what is represented by, say, the type \pcode{char})). +So $\sim{}r$ means `all the strings that $r$ cannot match'. Be careful that your implementation of $nullable$ and $der$ satisfies @@ -108,6 +110,14 @@ \end{tabular} \end{center} +\noindent +Remember your definitions have to satisfy the two properties + +\begin{itemize} +\item $nullable(r)$ if and only if $[]\in L(r)$ +\item $L(der\,c\,r)) = Der\,c\,(L(r))$ +\end{itemize} + \subsection*{Question 3 (marked with 1\%)} Implement the following regular expression for email addresses @@ -130,7 +140,7 @@ $\epsilon \cdot r$ & $\mapsto$ & $r$\\ $r + \varnothing$ & $\mapsto$ & $r$\\ $\varnothing + r$ & $\mapsto$ & $r$\\ -$r + r$ & $\mapsto$ & $r$ & (added on 12 October)\\ +$r + r$ & $\mapsto$ & $r$\\ \end{tabular} \end{center}