\usepackage{array}

\newcolumntype{C}[1]{>{\centering}m{#1}}

\subsection*{Task}

  $[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\

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

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

  $r^{\{n\}}$ & exactly $n$-times\\

  $r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\

  $r^{\{n..\}}$ & at least $n$-times $r$\\

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

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

\noindent You can assume that $n$ and $m$ are greater or equal than

$0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip

\noindent {\bf Important!} Your implementation should have explicit

cases for the basic regular expressions, but also explicit cases for

the extended regular expressions. That means do not treat the extended

regular expressions by just translating them into the basic ones. See

also Question 2, where you are asked to explicitly give the rules for

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

expressions.\newpage

\noindent

The meanings of the extended regular expressions are

  $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\}})$             & $\dn$ & $L(r)^n$\\

  $L(r^{\{..m\}})$           & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\

  $L(r^{\{n..\}})$           & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\

  $L(r^{\{n..m\}})$          & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\

  $L(\sim{}r)$              & $\dn$ & $\Sigma^* - L(r)$

means in effect ``all the strings that $r$ cannot match''.\medskip 

\noindent

\textit{der} satisfies for every regular expression $r$ the following

two properties (see also Question 2):

Question 4)?

  $\textit{nullable}([c_1,c_2,\ldots,c_n])$  & $\dn$ & $?$\\

  $\textit{nullable}(r^+)$                   & $\dn$ & $?$\\

  $\textit{nullable}(r^?)$                   & $\dn$ & $?$\\

  $\textit{nullable}(r^{\{n\}})$              & $\dn$ & $?$\\

  $\textit{nullable}(r^{\{..m\}})$            & $\dn$ & $?$\\

  $\textit{nullable}(r^{\{n..\}})$            & $\dn$ & $?$\\

  $\textit{nullable}(r^{\{n..m\}})$           & $\dn$ & $?$\\

  $\textit{nullable}(\sim{}r)$              & $\dn$ & $?$

\end{tabular}

\end{center}

\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\}})$              & $\dn$ & $?$\\

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

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

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

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

Given the definitions of \textit{nullable} and \textit{der}, it is

easy to implement a regular expression matcher.  Test your regular

expression matcher with (at least) the examples:

\begin{center}

\def\arraystretch{1.2}  

\begin{tabular}{r|m{12mm}|m{12mm}|m{12mm}|m{12mm}|m{12mm}|m{12mm}}

  string & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ &

     $(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$\\\hline

  $[]$           &&&&&& \\\hline 

  \texttt{a}     &&&&&& \\\hline 

  \texttt{aa}    &&&&&& \\\hline 

  \texttt{aaa}   &&&&&& \\\hline 

  \texttt{aaaaa} &&&&&& \\\hline 

  \texttt{aaaaaa}&&&&&& \\

\end{tabular}

\end{center}

\noindent

Does your matcher produce the expected results?

There are a number of explicit regular expressions that deal with single or several

characters, for example:

\begin{center}

\begin{tabular}{ll}

  $c$ & match a single character\\  

  $[c_1,c_2,\ldots,c_n]$ & match a set of characters---for character ranges\\

  $\textit{ALL}$ & match any character

\end{tabular}

\end{center}

\noindent

the latter is useful for matching any string (for example

$\textit{ALL}^*$). In order to avoid having an explicit constructor

for each case, we can generalise all such cases and introduce a single

constructor $\textit{CFUN}(f)$ where $f$ is a function from characters

to a boolean. Implement

\begin{center}

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

  $\textit{nullable}(\textit{CFUN}(f))$  & $\dn$ & $?$\\

  $\textit{der}\,c\,(\textit{CFUN}(f))$  & $\dn$ & $?$

\end{tabular}

\end{center}

\noindent in your matcher and then give definitions for

\begin{center}

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

  $c$  & $\dn$ & $\textit{CFUN}(?)$\\

  $[c_1,c_2,\ldots,c_n]$  & $\dn$ & $\textit{CFUN}(?)$\\

  $\textit{ALL}$  & $\dn$ & $\textit{CFUN}(?)$

\end{tabular}

\end{center}

\subsection*{Question 4}

Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression

\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\]

\noindent

Define in your code 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\}})

instead of code.\bigskip

\noindent

Implement the simplification rules in your regular expression matcher.

Consider the regular expression $/ \cdot * \cdot

(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *

Also let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be

\setcounter{enumi}{4}