afl-material: comparison coursework/cw01.tex

equal deleted inserted replaced

-:2f9fe225ecc8
+:e57d3d92b856
 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
-be awarded. However, the coursework will \emph{only} be judged
+be awarded. You can submit your answers in a txt-file or pdf.
-according to the answers. You can submit your answers in a
-txt-file or pdf.
 \subsubsection*{Disclaimer}
-It should be understood that the work you submit represents your own
+It should be understood that the work you submit represents
-effort.  You have not copied from anyone else. An exception is the
+your own effort. You have not copied from anyone else. An
-Scala code I showed during the lectures, which you can use.\bigskip
+exception is the Scala code I showed during the lectures or
+uploaded to KEATS, which you can use.\bigskip
 \subsubsection*{Tasks}
 The task is to implement a regular expression matcher based on
 $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}
-\noindent
+\noindent In the case of $r^{\{n,m\}}$ we have the convention
-In the case of $r^{\{n,m\}}$ we have the convention that $0 \le n \le m$.
+that $0 \le n \le m$. The meanings of the extended regular
-The meaning of these regular expressions is
+expressions are
 \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^{\{n,m\}})$           & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\
 $L(\sim{}r)$              & $\dn$ & $\Sigma^* - L(r)$
 \end{tabular}
 \end{center}
-\noindent
+\noindent whereby in the last clause the set $\Sigma^*$ stands
-whereby in the last clause the set $\Sigma^*$ stands for the set of
+for the set of \emph{all} strings over the alphabet $\Sigma$
-\emph{all} strings over the alphabet $\Sigma$ (in the implementation the
+(in the implementation the alphabet can be just what is
-alphabet can be just what is represented by, say, the type \pcode{char})).
+represented by, say, the type \pcode{char}). So $\sim{}r$
-So $\sim{}r$ means `all the strings that $r$
+means `all the strings that $r$ cannot match'.
-cannot match'.
+Be careful that your implementation of \textit{nullable} and
-Be careful that your implementation of $nullable$ and $der$ satisfies
+\textit{der} satisfies for every $r$ the following two
-for every $r$ the following two properties (see also Question 2):
+properties (see also Question 2):
 \begin{itemize}
-\item $nullable(r)$ if and only if $[]\in L(r)$
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
-\item $L(der\,c\,r)) = Der\,c\,(L(r))$
+\item $L(der\,c\,r) = Der\,c\,(L(r))$
 \end{itemize}
-\noindent
+\noindent {\bf Important!} Your implementation should have
-{\bf Important!} Your implementation should have explicit cases for
+explicit cases for the basic regular expressions, but also
-the basic regular expressions, but also explicit cases for the
+explicit cases for the extended regular expressions. That
-extended regular expressions.  That means do not treat the extended
+means do not treat the extended regular expressions by just
-regular expressions by just translating them into the basic ones. See
+translating them into the basic ones. See also Question 2,
-also Question 2, where you are asked to explicitly give the rules for
+where you are asked to explicitly give the rules for
 \textit{nullable} and \textit{der} for the extended regular
 expressions.
 \subsection*{Question 1 (unmarked)}
-What is your King's email address (you will need it in Question 3)?
+What is your King's email address (you will need it in
+Question 3)?
 \subsection*{Question 2 (marked with 2\%)}
-This question does not require any implementation. From the lectures
+This question does not require any implementation. From the
-you have seen the definitions for the functions \textit{nullable} and
+lectures you have seen the definitions for the functions
-\textit{der} for the basic regular expressions.  Give the rules for
+\textit{nullable} and \textit{der} for the basic regular
-the extended regular expressions:
+expressions. Give the rules for the extended regular
+expressions:
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-$nullable([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
+$\textit{nullable}([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
-$nullable(r^+)$                   & $\dn$ & $?$\\
+$\textit{nullable}(r^+)$                   & $\dn$ & $?$\\
-$nullable(r^?)$                   & $\dn$ & $?$\\
+$\textit{nullable}(r^?)$                   & $\dn$ & $?$\\
-$nullable(r^{\{n,m\}})$            & $\dn$ & $?$\\
+$\textit{nullable}(r^{\{n,m\}})$            & $\dn$ & $?$\\
-$nullable(\sim{}r)$               & $\dn$ & $?$\medskip\\
+$\textit{nullable}(\sim{}r)$               & $\dn$ & $?$\medskip\\
 $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$ & $?$\\
 \noindent
 Remember your definitions have to satisfy the two properties
 \begin{itemize}
-\item $nullable(r)$ if and only if $[]\in L(r)$
+\item $\textit{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\%)}
 \[
 ([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
 \]
-\noindent
+\noindent and calculate the derivative according to your email
-and calculate the derivative according to your email address. When
+address. When calculating the derivative, simplify all regular
-calculating the derivative, simplify all regular expressions as much
+expressions as much as possible, but at least apply the
-as possible, but at least apply the following six simplification
+following six simplification rules:
-rules:
 \begin{center}
 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
 $r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\
 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\
 \end{tabular}
 \end{center}
 \noindent
 Write down your simplified derivative in the ``mathematicical''
-notation using parentheses where necessary.
+notation using parentheses where necessary. That means you should
+use the more readable infix notation $+$, $\cdot$ and $^*$,
+instead of code.
 \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 *

changeset 395	e57d3d92b856
parent 358	b3129cff41e9
child 418	010c5a03dca2