updated
authorChristian Urban <christian dot urban at kcl dot ac dot uk>
Tue, 12 Jan 2016 02:18:58 +0000
changeset 395 e57d3d92b856
parent 394 2f9fe225ecc8
child 396 4cd75c619e06
updated
coursework/cw01.pdf
coursework/cw01.tex
coursework/cw02.pdf
coursework/cw02.tex
coursework/cw03.pdf
handouts/ho01.pdf
handouts/ho01.tex
style.sty
Binary file coursework/cw01.pdf has changed
--- a/coursework/cw01.tex	Tue Jan 05 01:46:41 2016 +0000
+++ b/coursework/cw01.tex	Tue Jan 12 02:18:58 2016 +0000
@@ -12,17 +12,16 @@
 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
-according to the answers. You can submit your answers in a
-txt-file or pdf.
+be awarded. 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
-effort.  You have not copied from anyone else. An exception is the
-Scala code I showed during the lectures, which you can use.\bigskip
+It should be understood that the work you submit represents
+your own effort. You have not copied from anyone else. An
+exception is the Scala code I showed during the lectures or
+uploaded to KEATS, which you can use.\bigskip
 
 
 \subsubsection*{Tasks}
@@ -48,9 +47,9 @@
 \end{tabular}
 \end{center}
 
-\noindent
-In the case of $r^{\{n,m\}}$ we have the convention that $0 \le n \le m$.
-The meaning of these regular expressions is
+\noindent In the case of $r^{\{n,m\}}$ we have the convention
+that $0 \le n \le m$. The meanings of the extended regular
+expressions are
 
 \begin{center}
 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
@@ -62,49 +61,51 @@
 \end{tabular}
 \end{center}
 
-\noindent
-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'. 
+\noindent 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
-for every $r$ the following two properties (see also Question 2):
+Be careful that your implementation of \textit{nullable} and
+\textit{der} satisfies for every $r$ the following two
+properties (see also Question 2):
 
 \begin{itemize}
-\item $nullable(r)$ if and only if $[]\in L(r)$
-\item $L(der\,c\,r)) = Der\,c\,(L(r))$
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r) = Der\,c\,(L(r))$
 \end{itemize}
 
-\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
+\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.
 
 
 \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
-you have seen the definitions for the functions \textit{nullable} and
-\textit{der} for the basic regular expressions.  Give the rules for
-the extended regular expressions:
+This question does not require any implementation. From the
+lectures you have seen the definitions for the functions
+\textit{nullable} and \textit{der} for the basic regular
+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$ & $?$\\
-$nullable(r^+)$                   & $\dn$ & $?$\\
-$nullable(r^?)$                   & $\dn$ & $?$\\
-$nullable(r^{\{n,m\}})$            & $\dn$ & $?$\\
-$nullable(\sim{}r)$               & $\dn$ & $?$\medskip\\
+$\textit{nullable}([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
+$\textit{nullable}(r^+)$                   & $\dn$ & $?$\\
+$\textit{nullable}(r^?)$                   & $\dn$ & $?$\\
+$\textit{nullable}(r^{\{n,m\}})$            & $\dn$ & $?$\\
+$\textit{nullable}(\sim{}r)$               & $\dn$ & $?$\medskip\\
 $der\, c\, ([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
 $der\, c\, (r^+)$                   & $\dn$ & $?$\\
 $der\, c\, (r^?)$                   & $\dn$ & $?$\\
@@ -117,7 +118,7 @@
 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}
 
@@ -129,11 +130,10 @@
 ([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
 \]
 
-\noindent
-and calculate the derivative according to your email address. When
-calculating the derivative, simplify all regular expressions as much
-as possible, but at least apply the following six simplification
-rules:
+\noindent and calculate the derivative according to your email
+address. When calculating the derivative, simplify all regular
+expressions as much as possible, but at least apply the
+following six simplification rules:
 
 \begin{center}
 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
@@ -149,8 +149,10 @@
 
 \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
Binary file coursework/cw02.pdf has changed
--- a/coursework/cw02.tex	Tue Jan 05 01:46:41 2016 +0000
+++ b/coursework/cw02.tex	Tue Jan 12 02:18:58 2016 +0000
@@ -11,9 +11,8 @@
 Lu tokeniser for the WHILE language. 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 according to the
-answers. You can submit your answers in a txt-file or as pdf.
+questions, otherwise a mark of 0\% will be awarded. You can
+submit your answers in a txt-file or as pdf.
 
 \subsection*{Disclaimer}
 
@@ -93,7 +92,7 @@
 \end{center}
 
 \noindent
-Try to design regular expressions to be as small as possible.
+Try to design your regular expressions to be as small as possible.
 
 \subsection*{Question 2 (marked with 3\%)}
 
Binary file coursework/cw03.pdf has changed
Binary file handouts/ho01.pdf has changed
--- a/handouts/ho01.tex	Tue Jan 05 01:46:41 2016 +0000
+++ b/handouts/ho01.tex	Tue Jan 12 02:18:58 2016 +0000
@@ -7,6 +7,7 @@
 %%http://regexcrossword.com/challenges/cities/puzzles/1
 
 \begin{document}
+\fnote{\copyright{} Christian Urban, 2014, 2015}
 
 \section*{Handout 1}
 
@@ -16,15 +17,16 @@
 Knuth-Morris-Pratt algorithm, which is currently the most
 efficient general string search algorithm. But often we do
 \emph{not} just look for a particular string, but for string
-patterns. For example in program code we need to identify
-what are the keywords, what are the identifiers etc. A pattern
-for identifiers could be stated as: they start with a letter,
+patterns. For example in program code we need to identify what
+are the keywords, what are the identifiers etc. A pattern for
+identifiers could be stated as: they start with a letter,
 followed by zero or more letters, numbers and underscores.
 Also often we face the problem that we are given a string (for
 example some user input) and want to know whether it matches a
-particular pattern. In this way we can exclude user input that
-would otherwise have nasty effects on our program (crashing it
-or making it go into an infinite loop, if not worse).
+particular pattern. In this way we can, for example, exclude
+user input that would otherwise have nasty effects on our
+program (crashing it or making it go into an infinite loop, if
+not worse).
 
 \defn{Regular expressions} help with conveniently specifying
 such patterns. The idea behind regular expressions is that
--- a/style.sty	Tue Jan 05 01:46:41 2016 +0000
+++ b/style.sty	Tue Jan 12 02:18:58 2016 +0000
@@ -42,6 +42,10 @@
 
 \definecolor{codegray}{gray}{0.9}
 
+\makeatletter
+\def\fnote{\gdef\@thefnmark{}\@footnotetext}
+\makeatother
+
 \newcommand{\HEADER}{{\bf Please submit your solutions via email. Please submit 
 only ASCII text or PDFs. Every solution should be preceeded by the corresponding 
 question, like: