# HG changeset patch # User Christian Urban # Date 1452565138 0 # Node ID e57d3d92b8562981411579e09fd876ab392b00b0 # Parent 2f9fe225ecc801a6620df3e9b3e0f4e3ccd66069 updated diff -r 2f9fe225ecc8 -r e57d3d92b856 coursework/cw01.pdf Binary file coursework/cw01.pdf has changed diff -r 2f9fe225ecc8 -r e57d3d92b856 coursework/cw01.tex --- 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 diff -r 2f9fe225ecc8 -r e57d3d92b856 coursework/cw02.pdf Binary file coursework/cw02.pdf has changed diff -r 2f9fe225ecc8 -r e57d3d92b856 coursework/cw02.tex --- 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\%)} diff -r 2f9fe225ecc8 -r e57d3d92b856 coursework/cw03.pdf Binary file coursework/cw03.pdf has changed diff -r 2f9fe225ecc8 -r e57d3d92b856 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 2f9fe225ecc8 -r e57d3d92b856 handouts/ho01.tex --- 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 diff -r 2f9fe225ecc8 -r e57d3d92b856 style.sty --- 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: