cws/cw01.tex
author Christian Urban <christian.urban@kcl.ac.uk>
Fri, 15 Sep 2023 10:49:33 +0100
changeset 918 53e7da9f372a
parent 907 8160c55991b9
child 938 91c20364402b
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
630
9b1c15c3eb6f updated
Christian Urban <urbanc@in.tum.de>
parents: 577
diff changeset
     1
% !TEX program = xelatex
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     2
\documentclass{article}
253
75c469893514 added coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 216
diff changeset
     3
\usepackage{../style}
216
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
     4
\usepackage{../langs}
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
     5
\usepackage[normalem]{ulem}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     6
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
     7
\usepackage{array}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
     8
888
fc812b8f120f texupdate
Christian Urban <christian.urban@kcl.ac.uk>
parents: 886
diff changeset
     9
%TEST
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    10
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    11
\begin{document}
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    12
\newcolumntype{C}[1]{>{\centering}m{#1}}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    13
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    14
\section*{Coursework 1}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    15
877
43460c7b2010 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 833
diff changeset
    16
This coursework is worth 5\% and is due on \cwONE{} at 16:00. You are
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    17
asked to implement a regular expression matcher and submit a document
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    18
containing the answers for the questions below. You can do the
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    19
implementation in any programming language you like, but you need to
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    20
submit the source code with which you answered the questions,
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    21
otherwise a mark of 0\% will be awarded. You need to submit your written
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    22
answers as pdf---see attached questionaire.  Code send as code. If you use
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    23
Scala in your code, a good place to start is the file \texttt{re3.sc}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    24
that is uploaded to Github.
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    25
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    26
%Please package everything
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    27
%inside a zip-file that creates a directory with the name
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    28
%\[\texttt{YournameYourfamilyname}\]
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    29
%
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    30
%\noindent on my end. Thanks!
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 351
diff changeset
    31
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 351
diff changeset
    32
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
    33
750
e93a9e74ca8e updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 748
diff changeset
    34
\subsubsection*{Disclaimer\alert}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    35
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
    36
It should be understood that the work you submit represents
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    37
your \textbf{own} effort. You have not copied from anyone else
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    38
including CoPilot, ChatGPT \& Co. An
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
    39
exception is the Scala code I showed during the lectures or
886
8a8d87394608 texupdate
Christian Urban <christian.urban@kcl.ac.uk>
parents: 877
diff changeset
    40
uploaded to KEATS, which you can freely use. Do not
8a8d87394608 texupdate
Christian Urban <christian.urban@kcl.ac.uk>
parents: 877
diff changeset
    41
be tempted to ask Github Copilot for help or do any other
8a8d87394608 texupdate
Christian Urban <christian.urban@kcl.ac.uk>
parents: 877
diff changeset
    42
shenanigans like this!\bigskip
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
    43
512
a6aa52ecc1c5 updated
cu
parents: 499
diff changeset
    44
\noindent
a6aa52ecc1c5 updated
cu
parents: 499
diff changeset
    45
If you have any questions, please send me an email in \textbf{good}
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
    46
time!\bigskip
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
    47
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    48
\subsection*{Task}
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
    49
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
    50
The task is to implement a regular expression matcher based on
418
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
    51
derivatives of regular expressions. The implementation should
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
    52
be able to deal with the usual (basic) regular expressions
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    53
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    54
\[
418
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
    55
\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    56
\]
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    57
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    58
\noindent
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
    59
but also with the following extended regular expressions:
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    60
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    61
\begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    62
\begin{tabular}{ll}
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    63
  $[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    64
  $r^+$ & one or more times $r$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    65
  $r^?$ & optional $r$\\
907
8160c55991b9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 888
diff changeset
    66
  $r_1 \,\&\, r_2$ & intersection (matched by both $r_1$ and $r_2$)\\
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    67
  $r^{\{n\}}$ & exactly $n$-times\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    68
  $r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    69
  $r^{\{n..\}}$ & at least $n$-times $r$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    70
  $r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    71
  $\sim{}r$ & not-regular-expression of $r$\\
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    72
\end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    73
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    74
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    75
\noindent You can assume that $n$ and $m$ are greater or equal than
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    76
$0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    77
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    78
\noindent {\bf Important!} Your implementation should have explicit
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
    79
case classes  for the basic regular expressions, but also explicit case
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
    80
classes for
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
    81
the extended regular expressions.\footnote{Please call them
907
8160c55991b9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 888
diff changeset
    82
  \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{AND}, \code{NTIMES},
630
9b1c15c3eb6f updated
Christian Urban <urbanc@in.tum.de>
parents: 577
diff changeset
    83
  \code{UPTO}, \code{FROM} and \code{BETWEEN}.} 
9b1c15c3eb6f updated
Christian Urban <urbanc@in.tum.de>
parents: 577
diff changeset
    84
  That means do not treat the extended regular expressions
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
    85
by just translating them into the basic ones. See also Question 3,
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
    86
where you are asked to explicitly give the rules for \textit{nullable}
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    87
and \textit{der} for the extended regular expressions. Something like
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    88
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    89
\[der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)\]
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    90
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    91
\noindent is \emph{not} allowed as answer in Question 3 and \emph{not}
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
    92
allowed in your code.\medskip
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    93
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    94
\noindent
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    95
The meanings of the extended regular expressions are
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    96
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    97
\begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    98
\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
    99
  $L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ 
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   100
  $L(r^+)$                  & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   101
  $L(r^?)$                  & $\dn$ & $L(r) \cup \{[]\}$\\
907
8160c55991b9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 888
diff changeset
   102
  $L(r_1 \,\&\, r_2)$       & $\dn$ & $L(r_1) \cap L(r_2)$\\
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   103
  $L(r^{\{n\}})$             & $\dn$ & $L(r)^n$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   104
  $L(r^{\{..m\}})$           & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   105
  $L(r^{\{n..\}})$           & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   106
  $L(r^{\{n..m\}})$          & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   107
  $L(\sim{}r)$              & $\dn$ & $\Sigma^* - L(r)$
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   108
\end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   109
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   110
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   111
\noindent whereby in the last clause the set $\Sigma^*$ stands
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   112
for the set of \emph{all} strings over the alphabet $\Sigma$
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   113
(in the implementation the alphabet can be just what is
418
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
   114
represented by, say, the type \pcode{Char}). So $\sim{}r$
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   115
means in effect ``all the strings that $r$ cannot match''.\medskip 
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   116
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   117
\noindent
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   118
Be careful that your implementation of \textit{nullable} and
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   119
\textit{der} satisfies for every regular expression $r$ the following
545
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   120
two properties (see also Question 3):
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   121
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   122
\begin{itemize}
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   123
\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   124
\item $L(der\,c\,r) = Der\,c\,(L(r))$
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   125
\end{itemize}
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   126
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   127
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   128
512
a6aa52ecc1c5 updated
cu
parents: 499
diff changeset
   129
\subsection*{Question 1 (Unmarked)}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   130
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   131
What is your King's email address (you will need it in
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   132
Question 5)? Also, could you please let me know whether you are
907
8160c55991b9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 888
diff changeset
   133
a BSc / MSci and the year you are in (in case of MSci). Thanks!
8160c55991b9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 888
diff changeset
   134
545
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   135
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   136
\subsection*{Question 2 (Unmarked)}
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   137
833
aad5957eb7e4 cwupdates
Christian Urban <christian.urban@kcl.ac.uk>
parents: 772
diff changeset
   138
Can you please also list all programming languages in which you have
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   139
already written programs (include only instances where you have spent
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   140
at least a good working day fiddling with a program)?  This is just
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   141
for my curiosity to estimate what your background is.
545
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   142
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   143
\subsection*{Question 3}
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   144
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   145
From the lectures you have seen the definitions for the functions
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   146
\textit{nullable} and \textit{der} for the basic regular
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   147
expressions. Implement and \underline{write down} the rules for the
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   148
extended regular expressions (see questionaire at the end).
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   149
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   150
333
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   151
\noindent
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   152
Remember your definitions have to satisfy the two properties
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   153
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   154
\begin{itemize}
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   155
\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
333
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   156
\item $L(der\,c\,r)) = Der\,c\,(L(r))$
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   157
\end{itemize}
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   158
473
dc528091eb70 updated
Christian Urban <urbanc@in.tum.de>
parents: 456
diff changeset
   159
\noindent
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   160
Given the definitions of \textit{nullable} and \textit{der}, it is
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   161
easy to implement a regular expression matcher.  Test your regular
907
8160c55991b9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 888
diff changeset
   162
expression matcher with (\underline{at least}) the examples:
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   163
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   164
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   165
\begin{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   166
\def\arraystretch{1.2}  
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   167
\begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}}
718
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   168
  string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ &
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   169
     $(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   170
  $[]$           &&&&&&& \\\hline 
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   171
  \texttt{a}     &&&&&&& \\\hline 
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   172
  \texttt{aa}    &&&&&&& \\\hline 
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   173
  \texttt{aaa}   &&&&&&& \\\hline 
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   174
  \texttt{aaaaa} &&&&&&& \\\hline 
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   175
  \texttt{aaaaaa}&&&&&&& \\
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   176
\end{tabular}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   177
\end{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   178
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   179
\noindent
718
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   180
Does your matcher produce the expected results? Make sure you
b7f9460c6a1c updated
Christian Urban <urbanc@in.tum.de>
parents: 630
diff changeset
   181
also test corner-cases, like $a^{\{0\}}$!
473
dc528091eb70 updated
Christian Urban <urbanc@in.tum.de>
parents: 456
diff changeset
   182
545
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   183
\subsection*{Question 4}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   184
494
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   185
As you can see, there are a number of explicit regular expressions
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   186
that deal with single or several characters, for example:
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   187
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   188
\begin{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   189
\begin{tabular}{ll}
494
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   190
  $c$ & matches a single character\\  
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   191
  $[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   192
  $\textit{ALL}$ & matches any character
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   193
\end{tabular}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   194
\end{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   195
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   196
\noindent
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   197
The latter is useful for matching any string (for example
494
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   198
by using $\textit{ALL}^*$). In order to avoid having an explicit constructor
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   199
for each case, we can generalise all these cases and introduce a single
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   200
constructor $\textit{CFUN}(f)$ where $f$ is a function from characters
576
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   201
to booleans. In Scala code this would look as follows:
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   202
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   203
\begin{lstlisting}[numbers=none]
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   204
abstract class Rexp
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   205
...
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   206
case class CFUN(f: Char => Boolean) extends Rexp 
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   207
\end{lstlisting}\smallskip
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   208
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   209
\noindent
550186034b6e updated
Christian Urban <urbanc@in.tum.de>
parents: 567
diff changeset
   210
The idea is that the function $f$ determines which character(s)
494
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   211
are matched, namely those where $f$ returns \texttt{true}.
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   212
In this question implement \textit{CFUN} and define
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   213
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   214
\begin{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   215
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   216
  $\textit{nullable}(\textit{CFUN}(f))$  & $\dn$ & $?$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   217
  $\textit{der}\,c\,(\textit{CFUN}(f))$  & $\dn$ & $?$
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   218
\end{tabular}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   219
\end{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   220
494
d0fc671bcbbf updated
Christian Urban <urbanc@in.tum.de>
parents: 492
diff changeset
   221
\noindent in your matcher and then also give definitions for
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   222
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   223
\begin{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   224
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   225
  $c$  & $\dn$ & $\textit{CFUN}(?)$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   226
  $[c_1,c_2,\ldots,c_n]$  & $\dn$ & $\textit{CFUN}(?)$\\
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   227
  $\textit{ALL}$  & $\dn$ & $\textit{CFUN}(?)$
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   228
\end{tabular}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   229
\end{center}
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   230
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   231
\noindent
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   232
You can either add the constructor $CFUN$ to your implementation in
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   233
Question 3, or you can implement this questions first
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   234
and then use $CFUN$ instead of \code{RANGE} and \code{CHAR} in Question 3.
833
aad5957eb7e4 cwupdates
Christian Urban <christian.urban@kcl.ac.uk>
parents: 772
diff changeset
   235
In an ideal world one would do this task first, but this might confuse
aad5957eb7e4 cwupdates
Christian Urban <christian.urban@kcl.ac.uk>
parents: 772
diff changeset
   236
you with what you need to do in the previous question.
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   237
545
76a98ed71a2a updated
Christian Urban <urbanc@in.tum.de>
parents: 512
diff changeset
   238
\subsection*{Question 5}
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   239
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   240
Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   241
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   242
\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\]
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   243
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   244
\noindent
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   245
Define in your code the following regular expression for email addresses
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   246
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   247
\[
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   248
([a\mbox{-}z0\mbox{-}9\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   249
\]
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   250
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   251
\noindent and calculate the derivative according to your own email
395
e57d3d92b856 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   252
address. When calculating the derivative, simplify all regular
418
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
   253
expressions as much as possible by applying the
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
   254
following 7 simplification rules:
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   255
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   256
\begin{center}
272
1446bc47a294 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 260
diff changeset
   257
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
439
7611ace6a93b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 418
diff changeset
   258
$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ 
7611ace6a93b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 418
diff changeset
   259
$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ 
7611ace6a93b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 418
diff changeset
   260
$r \cdot \ONE$ & $\mapsto$ & $r$\\ 
7611ace6a93b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 418
diff changeset
   261
$\ONE \cdot r$ & $\mapsto$ & $r$\\ 
7611ace6a93b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 418
diff changeset
   262
$r + \ZERO$ & $\mapsto$ & $r$\\ 
7611ace6a93b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 418
diff changeset
   263
$\ZERO + r$ & $\mapsto$ & $r$\\ 
333
8890852e18b7 updated coursework
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 328
diff changeset
   264
$r + r$ & $\mapsto$ & $r$\\ 
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   265
\end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   266
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   267
418
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
   268
\noindent Write down your simplified derivative in a readable
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
   269
notation using parentheses where necessary. That means you
010c5a03dca2 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 395
diff changeset
   270
should use the infix notation $+$, $\cdot$, $^*$ and so on,
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   271
instead of raw code.\bigskip
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   272
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   273
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   274
\subsection*{Question 6}
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   275
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   276
Implement the simplification rules in your regular expression matcher.
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   277
Consider the regular expression $/ \cdot * \cdot
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   278
(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *
630
9b1c15c3eb6f updated
Christian Urban <urbanc@in.tum.de>
parents: 577
diff changeset
   279
\cdot /$ and decide whether the following four strings are matched by
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   280
this regular expression. Answer yes or no.
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   281
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   282
\begin{enumerate}
216
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   283
\item \texttt{"/**/"}
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   284
\item \texttt{"/*foobar*/"}
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   285
\item \texttt{"/*test*/test*/"}
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   286
\item \texttt{"/*test/*test*/"}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   287
\end{enumerate}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   288
567
4573d36d0b2f updated
Christian Urban <urbanc@in.tum.de>
parents: 556
diff changeset
   289
\subsection*{Question 7}
512
a6aa52ecc1c5 updated
cu
parents: 499
diff changeset
   290
a6aa52ecc1c5 updated
cu
parents: 499
diff changeset
   291
Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
748
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   292
$(a^{\{19,19\}}) \cdot (a^?)$.\medskip
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   293
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   294
\noindent
383f2a5952ce updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 719
diff changeset
   295
Decide whether the following three
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   296
strings consisting of $a$s only can be matched by $(r_1^+)^+$.
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   297
Similarly test them with $(r_2^+)^+$. Again answer in all six cases
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   298
with yes or no. \medskip
130
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 129
diff changeset
   299
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 129
diff changeset
   300
\noindent
259
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   301
These are strings are meant to be entirely made up of $a$s. Be careful
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   302
when copy-and-pasting the strings so as to not forgetting any $a$ and
e5f4b8ff23b8 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 253
diff changeset
   303
to not introducing any other character.
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   304
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   305
\begin{enumerate}
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   306
\setcounter{enumi}{0}
216
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   307
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   308
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
216
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   309
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   310
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   311
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
216
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   312
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   313
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   314
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
216
f5ec7c597c5b updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 133
diff changeset
   315
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   316
\end{enumerate}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   317
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   318
\newpage
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   319
\section*{Answers}
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   320
918
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   321
\mbox{}  
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   322
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   323
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   324
\textbf{Name:}\uline{\hfill}\bigskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   325
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   326
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   327
\textbf{BSc / MSci \hspace{2cm} Year:\uline{\hspace{2cm}}}\bigskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   328
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   329
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   330
\textbf{Programming Languages:}\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   331
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   332
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   333
\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   334
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   335
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   336
\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   337
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   338
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   339
\uline{\hfill}\bigskip\bigskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   340
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   341
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   342
\textbf{Question 3:}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   343
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   344
\begin{center}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   345
\def\arraystretch{1.6}  
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   346
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   347
  $\textit{nullable}([c_1,c_2,\ldots,c_n])$  & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   348
  $\textit{nullable}(r^+)$                   & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   349
  $\textit{nullable}(r^?)$                   & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   350
  $\textit{nullable}(r_1 \,\&\, r_2)$        & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   351
  $\textit{nullable}(r^{\{n\}})$              & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   352
  & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   353
  $\textit{nullable}(r^{\{..m\}})$            & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   354
  & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   355
  $\textit{nullable}(r^{\{n..\}})$            & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   356
  & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   357
  $\textit{nullable}(r^{\{n..m\}})$           & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   358
  & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   359
  $\textit{nullable}(\sim{}r)$              & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   360
%  \\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   361
\end{tabular}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   362
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}  
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   363
  $der\, c\, ([c_1,c_2,\ldots,c_n])$  & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   364
  $der\, c\, (r^+)$                   & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   365
  $der\, c\, (r^?)$                   & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   366
  $der\, c\, (r_1 \,\&\, r_2)$        & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   367
  $der\, c\, (r^{\{n\}})$              & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   368
                                      & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   369
  $der\, c\, (r^{\{..m\}})$           & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   370
                                     &  & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   371
  $der\, c\, (r^{\{n..\}})$           & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   372
                                     & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   373
  $der\, c\, (r^{\{n..m\}})$           & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   374
                                      &  & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   375
                                      &  & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   376
  $der\, c\, (\sim{}r)$               & $\dn$ & \uline{\hspace{8cm}}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   377
\end{tabular}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   378
\end{center}\bigskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   379
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   380
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   381
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   382
\textbf{Question 4:}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   383
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   384
\begin{center}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   385
\def\arraystretch{1.6}    
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   386
\begin{tabular}{@ {}r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   387
  $\textit{nullable}(CFUN(f))$  & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   388
  \\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   389
  $der\, c\, (CFUN(f))$  & $\dn$ & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   390
                         & & \uline{\hspace{8cm}}\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   391
  \\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   392
  \\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   393
  $c$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   394
  $[c_1,c_2,\ldots,c_n]$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   395
  $\textit{ALL}$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   396
\end{tabular}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   397
\end{center}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   398
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   399
\newpage
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   400
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   401
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   402
\textbf{Question 5 (`mathematical' notation):}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   403
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   404
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   405
\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   406
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   407
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   408
\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   409
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   410
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   411
\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   412
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   413
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   414
\uline{\hfill}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   415
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   416
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   417
\uline{\hfill}\bigskip\bigskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   418
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   419
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   420
\textbf{Question 6:}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   421
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   422
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   423
\textbf{1)}\; Yes / No\qquad
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   424
\textbf{2)}\; Yes / No\qquad
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   425
\textbf{3)}\; Yes / No\qquad
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   426
\textbf{4)}\; Yes / No\bigskip\bigskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   427
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   428
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   429
\noindent
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   430
\textbf{Question 7:}\medskip
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   431
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   432
\def\arraystretch{1.5}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   433
\begin{tabular}{l|c|c}
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   434
  & $\quad{}r_1\quad$ & $\quad{}r_2\quad$\\\hline
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   435
  1. & & \\\hline
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   436
  2. & & \\\hline
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   437
  3. & & \\
53e7da9f372a updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 907
diff changeset
   438
\end{tabular}
492
39b7ff2cf1bc updated
Christian Urban <urbanc@in.tum.de>
parents: 473
diff changeset
   439
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   440
\end{document}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   441
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   442
%%% Local Variables: 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   443
%%% mode: latex
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   444
%%% TeX-master: t
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   445
%%% End: