# HG changeset patch # User Christian Urban # Date 1443480454 -3600 # Node ID 8890852e18b714883f50b81e3852a64ff47fd155 # Parent 4755ad4b457b5e2ca18e324b1c6dbce8181304f2 updated coursework diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw01.pdf Binary file coursework/cw01.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw01.tex --- a/coursework/cw01.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/coursework/cw01.tex Mon Sep 28 23:47:34 2015 +0100 @@ -55,13 +55,15 @@ $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$ & $\mathbb{A} - L(r)$ +$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ \end{tabular} \end{center} \noindent -whereby in the last clause the set $\mathbb{A}$ stands for the set of -\emph{all} strings. So $\sim{}r$ means `all the strings that $r$ +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 @@ -108,6 +110,14 @@ \end{tabular} \end{center} +\noindent +Remember your definitions have to satisfy the two properties + +\begin{itemize} +\item $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\%)} Implement the following regular expression for email addresses @@ -130,7 +140,7 @@ $\epsilon \cdot r$ & $\mapsto$ & $r$\\ $r + \varnothing$ & $\mapsto$ & $r$\\ $\varnothing + r$ & $\mapsto$ & $r$\\ -$r + r$ & $\mapsto$ & $r$ & (added on 12 October)\\ +$r + r$ & $\mapsto$ & $r$\\ \end{tabular} \end{center} diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw02.pdf Binary file coursework/cw02.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw02.tex --- a/coursework/cw02.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/coursework/cw02.tex Mon Sep 28 23:47:34 2015 +0100 @@ -92,8 +92,6 @@ \end{center} \noindent -Once you have designed all regular expressions for 1 - 8, then -give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}. \subsection*{Question 2 (marked with 3\%)} @@ -116,6 +114,7 @@ \noindent and use your \pcode{env} function to give the token sequence. + \subsection*{Question 3 (marked with 1\%)} Extend your tokenizer from Q2 to also simplify regular expressions diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw03.pdf Binary file coursework/cw03.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw03.tex --- a/coursework/cw03.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/coursework/cw03.tex Mon Sep 28 23:47:34 2015 +0100 @@ -7,7 +7,7 @@ \section*{Coursework 3 (Strand 1)} \noindent -This coursework is worth 5\% and is due on 27 November at 16:00. You +This coursework is worth 5\% and is due on 26 November at 16:00. You are asked to implement a parser for the WHILE language and also an interpreter. You should use the lexer from the previous coursework for the parser. diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw04.pdf Binary file coursework/cw04.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw04.tex --- a/coursework/cw04.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/coursework/cw04.tex Mon Sep 28 23:47:34 2015 +0100 @@ -88,7 +88,7 @@ \caption{The Fibonacci program in the WHILE language.\label{fibs}} \end{figure} -\subsection*{Question 2 (marked with 5\%)} +\subsection*{Question 2 (marked with 4\%)} Extend the syntax of you language so that it contains also \texttt{for}-loops, like @@ -133,6 +133,8 @@ \end{minipage} \end{center} +\subsection*{Question 3 (marked with 1\%)} + \noindent In this question you are supposed to give the assembler instructions for the program @@ -140,9 +142,9 @@ \begin{center} \begin{minipage}{6cm} \begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none] -for i := 1 upto 10000 do { - for i := 1 upto 10000 do { - skip +for i := 1 upto 10 do { + for i := 1 upto 10 do { + write i } } \end{lstlisting} @@ -152,6 +154,8 @@ \noindent Note that in this program the variable \pcode{i} is used twice. You need to make a decision how it should be compiled? +Explain you decision and indicate what this program would +print out. \subsection*{Further Information} diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw05.pdf Binary file coursework/cw05.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 coursework/cw05.tex --- a/coursework/cw05.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/coursework/cw05.tex Mon Sep 28 23:47:34 2015 +0100 @@ -7,7 +7,8 @@ \section*{Coursework (Strand 2)} \noindent This coursework is worth 25\% and is due on 11 -December at 16:00. You are asked to prove the correctness of a +December at 16:00. You are asked to prove the correctness of +the regular expression matcher from the lectures using the Isabelle theorem prover. You need to submit a theory file containing this proof. The Isabelle theorem prover is diff -r 4755ad4b457b -r 8890852e18b7 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 handouts/ho02.tex --- a/handouts/ho02.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/handouts/ho02.tex Mon Sep 28 23:47:34 2015 +0100 @@ -545,8 +545,9 @@ \lstinputlisting{../progs/app6.scala} \caption{The simplification function and modified \texttt{ders}-function; this function now -calls \texttt{der} first, but then tries to simplify -the resulting derivative regular expressions.\label{scala2}} +calls \texttt{der} first, but then simplifies +the resulting derivative regular expressions, see +Line~28.\label{scala2}} \end{figure} \begin{center} diff -r 4755ad4b457b -r 8890852e18b7 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 4755ad4b457b -r 8890852e18b7 handouts/ho03.tex --- a/handouts/ho03.tex Fri Sep 25 20:59:24 2015 +0100 +++ b/handouts/ho03.tex Mon Sep 28 23:47:34 2015 +0100 @@ -855,8 +855,9 @@ \section{Further Reading} -Compare what a human expert would create for $a (b + c)^*$ and -what the Thomson algorithm. +Compare what a ``human expert'' would create as automaton for the +regular expression $a (b + c)^*$ and what the Thomson +algorithm generates. %http://www.inf.ed.ac.uk/teaching/courses/ct/ \end{document}