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-- |
630 | 1 |
% !TEX program = xelatex |
127
41ef073ac6c4
added
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 | 5 |
\usepackage[normalem]{ulem} |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
492 | 7 |
\usepackage{array} |
8 |
||
888 | 9 |
%TEST |
492 | 10 |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
\begin{document} |
492 | 12 |
\newcolumntype{C}[1]{>{\centering}m{#1}} |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
|
748 | 14 |
\section*{Coursework 1} |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
15 |
|
877 | 16 |
This coursework is worth 5\% and is due on \cwONE{} at 16:00. You are |
748 | 17 |
asked to implement a regular expression matcher and submit a document |
18 |
containing the answers for the questions below. You can do the |
|
19 |
implementation in any programming language you like, but you need to |
|
20 |
submit the source code with which you answered the questions, |
|
918 | 21 |
otherwise a mark of 0\% will be awarded. You need to submit your written |
22 |
answers as pdf---see attached questionaire. Code send as code. If you use |
|
23 |
Scala in your code, a good place to start is the file \texttt{re3.sc} |
|
24 |
that is uploaded to Github. |
|
748 | 25 |
|
918 | 26 |
%Please package everything |
27 |
%inside a zip-file that creates a directory with the name |
|
28 |
%\[\texttt{YournameYourfamilyname}\] |
|
29 |
% |
|
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 | 34 |
\subsubsection*{Disclaimer\alert} |
127
41ef073ac6c4
added
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 | 37 |
your \textbf{own} effort. You have not copied from anyone else |
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 | 40 |
uploaded to KEATS, which you can freely use. Do not |
41 |
be tempted to ask Github Copilot for help or do any other |
|
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 | 44 |
\noindent |
45 |
If you have any questions, please send me an email in \textbf{good} |
|
918 | 46 |
time!\bigskip |
259
e5f4b8ff23b8
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
253
diff
changeset
|
47 |
|
492 | 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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
|
41ef073ac6c4
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
\] |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
|
41ef073ac6c4
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
60 |
|
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
\begin{center} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
\begin{tabular}{ll} |
492 | 63 |
$[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\ |
64 |
$r^+$ & one or more times $r$\\ |
|
65 |
$r^?$ & optional $r$\\ |
|
907 | 66 |
$r_1 \,\&\, r_2$ & intersection (matched by both $r_1$ and $r_2$)\\ |
492 | 67 |
$r^{\{n\}}$ & exactly $n$-times\\ |
68 |
$r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\ |
|
69 |
$r^{\{n..\}}$ & at least $n$-times $r$\\ |
|
70 |
$r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\ |
|
71 |
$\sim{}r$ & not-regular-expression of $r$\\ |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
72 |
\end{tabular} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
73 |
\end{center} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
|
492 | 75 |
\noindent You can assume that $n$ and $m$ are greater or equal than |
76 |
$0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip |
|
77 |
||
78 |
\noindent {\bf Important!} Your implementation should have explicit |
|
567 | 79 |
case classes for the basic regular expressions, but also explicit case |
80 |
classes for |
|
81 |
the extended regular expressions.\footnote{Please call them |
|
907 | 82 |
\code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{AND}, \code{NTIMES}, |
630 | 83 |
\code{UPTO}, \code{FROM} and \code{BETWEEN}.} |
84 |
That means do not treat the extended regular expressions |
|
567 | 85 |
by just translating them into the basic ones. See also Question 3, |
86 |
where you are asked to explicitly give the rules for \textit{nullable} |
|
748 | 87 |
and \textit{der} for the extended regular expressions. Something like |
88 |
||
89 |
\[der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)\] |
|
90 |
||
91 |
\noindent is \emph{not} allowed as answer in Question 3 and \emph{not} |
|
92 |
allowed in your code.\medskip |
|
492 | 93 |
|
94 |
\noindent |
|
95 |
The meanings of the extended regular expressions are |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
96 |
|
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
97 |
\begin{center} |
41ef073ac6c4
added
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 | 99 |
$L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ |
100 |
$L(r^+)$ & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\ |
|
101 |
$L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ |
|
907 | 102 |
$L(r_1 \,\&\, r_2)$ & $\dn$ & $L(r_1) \cap L(r_2)$\\ |
492 | 103 |
$L(r^{\{n\}})$ & $\dn$ & $L(r)^n$\\ |
104 |
$L(r^{\{..m\}})$ & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\ |
|
105 |
$L(r^{\{n..\}})$ & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\ |
|
106 |
$L(r^{\{n..m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\ |
|
107 |
$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
108 |
\end{tabular} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
109 |
\end{center} |
41ef073ac6c4
added
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 | 115 |
means in effect ``all the strings that $r$ cannot match''.\medskip |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
116 |
|
492 | 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 | 119 |
\textit{der} satisfies for every regular expression $r$ the following |
545 | 120 |
two properties (see also Question 3): |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
|
41ef073ac6c4
added
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
41ef073ac6c4
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
128 |
|
512 | 129 |
\subsection*{Question 1 (Unmarked)} |
127
41ef073ac6c4
added
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 | 132 |
Question 5)? Also, could you please let me know whether you are |
907 | 133 |
a BSc / MSci and the year you are in (in case of MSci). Thanks! |
134 |
||
545 | 135 |
|
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 | 138 |
Can you please also list all programming languages in which you have |
748 | 139 |
already written programs (include only instances where you have spent |
140 |
at least a good working day fiddling with a program)? This is just |
|
141 |
for my curiosity to estimate what your background is. |
|
545 | 142 |
|
143 |
\subsection*{Question 3} |
|
259
e5f4b8ff23b8
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
253
diff
changeset
|
144 |
|
918 | 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 | 147 |
expressions. Implement and \underline{write down} the rules for the |
148 |
extended regular expressions (see questionaire at the end). |
|
127
41ef073ac6c4
added
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 | 159 |
\noindent |
492 | 160 |
Given the definitions of \textit{nullable} and \textit{der}, it is |
161 |
easy to implement a regular expression matcher. Test your regular |
|
907 | 162 |
expression matcher with (\underline{at least}) the examples: |
492 | 163 |
|
164 |
||
165 |
\begin{center} |
|
166 |
\def\arraystretch{1.2} |
|
748 | 167 |
\begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}} |
718 | 168 |
string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ & |
169 |
$(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline |
|
170 |
$[]$ &&&&&&& \\\hline |
|
171 |
\texttt{a} &&&&&&& \\\hline |
|
172 |
\texttt{aa} &&&&&&& \\\hline |
|
173 |
\texttt{aaa} &&&&&&& \\\hline |
|
174 |
\texttt{aaaaa} &&&&&&& \\\hline |
|
175 |
\texttt{aaaaaa}&&&&&&& \\ |
|
492 | 176 |
\end{tabular} |
177 |
\end{center} |
|
178 |
||
179 |
\noindent |
|
718 | 180 |
Does your matcher produce the expected results? Make sure you |
181 |
also test corner-cases, like $a^{\{0\}}$! |
|
473 | 182 |
|
545 | 183 |
\subsection*{Question 4} |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
184 |
|
494 | 185 |
As you can see, there are a number of explicit regular expressions |
186 |
that deal with single or several characters, for example: |
|
492 | 187 |
|
188 |
\begin{center} |
|
189 |
\begin{tabular}{ll} |
|
494 | 190 |
$c$ & matches a single character\\ |
191 |
$[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\ |
|
192 |
$\textit{ALL}$ & matches any character |
|
492 | 193 |
\end{tabular} |
194 |
\end{center} |
|
195 |
||
196 |
\noindent |
|
567 | 197 |
The latter is useful for matching any string (for example |
494 | 198 |
by using $\textit{ALL}^*$). In order to avoid having an explicit constructor |
199 |
for each case, we can generalise all these cases and introduce a single |
|
492 | 200 |
constructor $\textit{CFUN}(f)$ where $f$ is a function from characters |
576 | 201 |
to booleans. In Scala code this would look as follows: |
202 |
||
203 |
\begin{lstlisting}[numbers=none] |
|
204 |
abstract class Rexp |
|
205 |
... |
|
206 |
case class CFUN(f: Char => Boolean) extends Rexp |
|
207 |
\end{lstlisting}\smallskip |
|
208 |
||
209 |
\noindent |
|
210 |
The idea is that the function $f$ determines which character(s) |
|
494 | 211 |
are matched, namely those where $f$ returns \texttt{true}. |
212 |
In this question implement \textit{CFUN} and define |
|
492 | 213 |
|
214 |
\begin{center} |
|
215 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
216 |
$\textit{nullable}(\textit{CFUN}(f))$ & $\dn$ & $?$\\ |
|
217 |
$\textit{der}\,c\,(\textit{CFUN}(f))$ & $\dn$ & $?$ |
|
218 |
\end{tabular} |
|
219 |
\end{center} |
|
220 |
||
494 | 221 |
\noindent in your matcher and then also give definitions for |
492 | 222 |
|
223 |
\begin{center} |
|
224 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
225 |
$c$ & $\dn$ & $\textit{CFUN}(?)$\\ |
|
226 |
$[c_1,c_2,\ldots,c_n]$ & $\dn$ & $\textit{CFUN}(?)$\\ |
|
227 |
$\textit{ALL}$ & $\dn$ & $\textit{CFUN}(?)$ |
|
228 |
\end{tabular} |
|
229 |
\end{center} |
|
230 |
||
567 | 231 |
\noindent |
232 |
You can either add the constructor $CFUN$ to your implementation in |
|
233 |
Question 3, or you can implement this questions first |
|
234 |
and then use $CFUN$ instead of \code{RANGE} and \code{CHAR} in Question 3. |
|
833 | 235 |
In an ideal world one would do this task first, but this might confuse |
236 |
you with what you need to do in the previous question. |
|
492 | 237 |
|
545 | 238 |
\subsection*{Question 5} |
492 | 239 |
|
240 |
Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression |
|
241 |
||
242 |
\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\] |
|
243 |
||
244 |
\noindent |
|
245 |
Define in your code the following regular expression for email addresses |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
246 |
|
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
247 |
\[ |
492 | 248 |
([a\mbox{-}z0\mbox{-}9\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}}) |
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
249 |
\] |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
250 |
|
567 | 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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
255 |
|
41ef073ac6c4
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
265 |
\end{tabular} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
266 |
\end{center} |
41ef073ac6c4
added
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 | 271 |
instead of raw code.\bigskip |
272 |
||
273 |
||
274 |
\subsection*{Question 6} |
|
275 |
||
492 | 276 |
Implement the simplification rules in your regular expression matcher. |
277 |
Consider the regular expression $/ \cdot * \cdot |
|
278 |
(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot * |
|
630 | 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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
281 |
|
41ef073ac6c4
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
287 |
\end{enumerate} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
288 |
|
567 | 289 |
\subsection*{Question 7} |
512 | 290 |
|
291 |
Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be |
|
748 | 292 |
$(a^{\{19,19\}}) \cdot (a^?)$.\medskip |
293 |
||
294 |
\noindent |
|
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
5c4998375c46
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
129
diff
changeset
|
299 |
|
5c4998375c46
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
304 |
|
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
305 |
\begin{enumerate} |
918 | 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
41ef073ac6c4
added
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
41ef073ac6c4
added
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
41ef073ac6c4
added
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
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
316 |
\end{enumerate} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
317 |
|
918 | 318 |
\newpage |
319 |
\section*{Answers} |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
320 |
|
918 | 321 |
\mbox{} |
322 |
||
323 |
\noindent |
|
324 |
\textbf{Name:}\uline{\hfill}\bigskip |
|
325 |
||
326 |
\noindent |
|
327 |
\textbf{BSc / MSci \hspace{2cm} Year:\uline{\hspace{2cm}}}\bigskip |
|
328 |
||
329 |
\noindent |
|
330 |
\textbf{Programming Languages:}\uline{\hfill}\medskip |
|
331 |
||
332 |
\noindent |
|
333 |
\uline{\hfill}\medskip |
|
334 |
||
335 |
\noindent |
|
336 |
\uline{\hfill}\medskip |
|
337 |
||
338 |
\noindent |
|
339 |
\uline{\hfill}\bigskip\bigskip |
|
340 |
||
341 |
\noindent |
|
342 |
\textbf{Question 3:} |
|
343 |
||
344 |
\begin{center} |
|
345 |
\def\arraystretch{1.6} |
|
346 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
347 |
$\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
348 |
$\textit{nullable}(r^+)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
349 |
$\textit{nullable}(r^?)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
350 |
$\textit{nullable}(r_1 \,\&\, r_2)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
351 |
$\textit{nullable}(r^{\{n\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
352 |
& & \uline{\hspace{8cm}}\\ |
|
353 |
$\textit{nullable}(r^{\{..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
354 |
& & \uline{\hspace{8cm}}\\ |
|
355 |
$\textit{nullable}(r^{\{n..\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
356 |
& & \uline{\hspace{8cm}}\\ |
|
357 |
$\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
358 |
& & \uline{\hspace{8cm}}\\ |
|
359 |
$\textit{nullable}(\sim{}r)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
360 |
% \\ |
|
361 |
\end{tabular} |
|
362 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
363 |
$der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
364 |
$der\, c\, (r^+)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
365 |
$der\, c\, (r^?)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
366 |
$der\, c\, (r_1 \,\&\, r_2)$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
367 |
$der\, c\, (r^{\{n\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
368 |
& & \uline{\hspace{8cm}}\\ |
|
369 |
$der\, c\, (r^{\{..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
370 |
& & \uline{\hspace{8cm}}\\ |
|
371 |
$der\, c\, (r^{\{n..\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
372 |
& & \uline{\hspace{8cm}}\\ |
|
373 |
$der\, c\, (r^{\{n..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
374 |
& & \uline{\hspace{8cm}}\\ |
|
375 |
& & \uline{\hspace{8cm}}\\ |
|
376 |
$der\, c\, (\sim{}r)$ & $\dn$ & \uline{\hspace{8cm}} |
|
377 |
\end{tabular} |
|
378 |
\end{center}\bigskip |
|
379 |
||
380 |
||
381 |
\noindent |
|
382 |
\textbf{Question 4:} |
|
383 |
||
384 |
\begin{center} |
|
385 |
\def\arraystretch{1.6} |
|
386 |
\begin{tabular}{@ {}r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
387 |
$\textit{nullable}(CFUN(f))$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
388 |
\\ |
|
389 |
$der\, c\, (CFUN(f))$ & $\dn$ & \uline{\hspace{8cm}}\\ |
|
390 |
& & \uline{\hspace{8cm}}\\ |
|
391 |
\\ |
|
392 |
\\ |
|
393 |
$c$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\ |
|
394 |
$[c_1,c_2,\ldots,c_n]$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\ |
|
395 |
$\textit{ALL}$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\ |
|
396 |
\end{tabular} |
|
397 |
\end{center} |
|
398 |
||
399 |
\newpage |
|
400 |
||
401 |
\noindent |
|
402 |
\textbf{Question 5 (`mathematical' notation):} |
|
403 |
||
404 |
\noindent |
|
405 |
\uline{\hfill}\medskip |
|
406 |
||
407 |
\noindent |
|
408 |
\uline{\hfill}\medskip |
|
409 |
||
410 |
\noindent |
|
411 |
\uline{\hfill}\medskip |
|
412 |
||
413 |
\noindent |
|
414 |
\uline{\hfill}\medskip |
|
415 |
||
416 |
\noindent |
|
417 |
\uline{\hfill}\bigskip\bigskip |
|
418 |
||
419 |
\noindent |
|
420 |
\textbf{Question 6:}\medskip |
|
421 |
||
422 |
\noindent |
|
423 |
\textbf{1)}\; Yes / No\qquad |
|
424 |
\textbf{2)}\; Yes / No\qquad |
|
425 |
\textbf{3)}\; Yes / No\qquad |
|
426 |
\textbf{4)}\; Yes / No\bigskip\bigskip |
|
427 |
||
428 |
||
429 |
\noindent |
|
430 |
\textbf{Question 7:}\medskip |
|
431 |
||
432 |
\def\arraystretch{1.5} |
|
433 |
\begin{tabular}{l|c|c} |
|
434 |
& $\quad{}r_1\quad$ & $\quad{}r_2\quad$\\\hline |
|
435 |
1. & & \\\hline |
|
436 |
2. & & \\\hline |
|
437 |
3. & & \\ |
|
438 |
\end{tabular} |
|
492 | 439 |
|
127
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
440 |
\end{document} |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
441 |
|
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
442 |
%%% Local Variables: |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
443 |
%%% mode: latex |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
444 |
%%% TeX-master: t |
41ef073ac6c4
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
445 |
%%% End: |