\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\begin{document}

\section*{Coursework 1 (Strand 1)}

This coursework is worth 5\% and is due on 20 October at

16:00. You are asked to implement a regular expression matcher

and submit a document containing the answers for the questions

below. You can do the implementation in any programming

language you like, but you need to submit the source code with

which you answered the questions, otherwise a mark of 0\% will

\subsubsection*{Disclaimer}

\subsubsection*{Tasks}

The task is to implement a regular expression matcher based on

derivatives. The implementation should be able to deal with the usual

(basic) regular expressions

\[

\varnothing, \epsilon, c, r_1 + r_2, r_1 \cdot r_2, r^*

\]

\noindent

but also with the following extended regular expressions:

\begin{center}

\begin{tabular}{ll}

$[c_1 c_2 \ldots c_n]$ & a range of characters\\

$r^+$ & one or more times $r$\\

$r^?$ & optional $r$\\

$r^{\{n,m\}}$ & at least $n$-times $r$ but no more than $m$-times\\

$\sim{}r$ & not-regular expression of $r$\\

\end{tabular}

\end{center}

\begin{center}

\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}

$L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ 

$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$ & $\Sigma^* - L(r)$

\end{tabular}

\end{center}

\begin{itemize}

\end{itemize}

\textit{nullable} and \textit{der} for the extended regular

expressions.

\subsection*{Question 1 (unmarked)}

\subsection*{Question 2 (marked with 2\%)}

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

$der\, c\, ([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\

$der\, c\, (r^+)$                   & $\dn$ & $?$\\

$der\, c\, (r^?)$                   & $\dn$ & $?$\\

$der\, c\, (r^{\{n,m\}})$            & $\dn$ & $?$\\

$der\, c\, (\sim{}r)$               & $\dn$ & $?$\\

\end{tabular}

\end{center}

\noindent

Remember your definitions have to satisfy the two properties

\begin{itemize}

\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

\[

([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})

\]

\begin{center}

\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}

$r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\ 

$\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\ 

$r \cdot \epsilon$ & $\mapsto$ & $r$\\ 

$\epsilon \cdot r$ & $\mapsto$ & $r$\\ 

$r + \varnothing$ & $\mapsto$ & $r$\\ 

$\varnothing + r$ & $\mapsto$ & $r$\\ 

$r + r$ & $\mapsto$ & $r$\\ 

\end{tabular}

\end{center}

\noindent

Write down your simplified derivative in the ``mathematicical''

\subsection*{Question 4 (marked with 1\%)}

Suppose \textit{[a-z]} stands for the range regular expression

$[a,b,c,\ldots,z]$.  Consider the regular expression $/ \cdot * \cdot

(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot *

\cdot /$ and decide wether the following four strings are matched by

this regular expression. Answer yes or no.

\begin{enumerate}

\item \texttt{"/**/"}

\item \texttt{"/*foobar*/"}

\item \texttt{"/*test*/test*/"}

\item \texttt{"/*test/*test*/"}

\end{enumerate}

\subsection*{Question 5 (marked with 1\%)}

Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be

$(a^{\{19,19\}}) \cdot (a^?)$.  Decide whether the following three

strings consisting of $a$s only can be matched by $(r_1^+)^+$.

Similarly test them with $(r_2^+)^+$. Again answer in all six cases

with yes or no. \medskip

\noindent

These are strings are meant to be entirely made up of $a$s. Be careful

when copy-and-pasting the strings so as to not forgetting any $a$ and

to not introducing any other character.

\begin{enumerate}

\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

\end{enumerate}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: