630
|
1 |
% !TEX program = xelatex
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
\documentclass{article}
|
253
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../style}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../langs}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
|
492
|
6 |
\usepackage{array}
|
|
7 |
|
|
8 |
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
\begin{document}
|
492
|
10 |
\newcolumntype{C}[1]{>{\centering}m{#1}}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
|
748
|
12 |
\section*{Coursework 1}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
|
748
|
14 |
This coursework is worth 5\% and is due on \cwONE{} at 18:00. You are
|
|
15 |
asked to implement a regular expression matcher and submit a document
|
|
16 |
containing the answers for the questions below. You can do the
|
|
17 |
implementation in any programming language you like, but you need to
|
|
18 |
submit the source code with which you answered the questions,
|
|
19 |
otherwise a mark of 0\% will be awarded. You can submit your answers
|
|
20 |
in a txt-file or pdf. Code send as code. Please package everything
|
|
21 |
inside a zip-file that creates a directory with the name
|
|
22 |
\[\texttt{YournameYourfamilyname}\]
|
|
23 |
|
|
24 |
\noindent on my end. Thanks!
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
|
750
|
28 |
\subsubsection*{Disclaimer\alert}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
It should be understood that the work you submit represents
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
your own effort. You have not copied from anyone else. An
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
exception is the Scala code I showed during the lectures or
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
uploaded to KEATS, which you can freely use.\bigskip
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
|
512
|
35 |
\noindent
|
|
36 |
If you have any questions, please send me an email in \textbf{good}
|
|
37 |
time.\bigskip
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
|
492
|
39 |
\subsection*{Task}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
The task is to implement a regular expression matcher based on
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
derivatives of regular expressions. The implementation should
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
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
|
44 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
\[
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
\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
|
47 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
\noindent
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
but also with the following extended regular expressions:
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
\begin{tabular}{ll}
|
492
|
54 |
$[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\
|
|
55 |
$r^+$ & one or more times $r$\\
|
|
56 |
$r^?$ & optional $r$\\
|
|
57 |
$r^{\{n\}}$ & exactly $n$-times\\
|
|
58 |
$r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\
|
|
59 |
$r^{\{n..\}}$ & at least $n$-times $r$\\
|
|
60 |
$r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\
|
|
61 |
$\sim{}r$ & not-regular-expression of $r$\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
|
492
|
65 |
\noindent You can assume that $n$ and $m$ are greater or equal than
|
|
66 |
$0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip
|
|
67 |
|
|
68 |
\noindent {\bf Important!} Your implementation should have explicit
|
567
|
69 |
case classes for the basic regular expressions, but also explicit case
|
|
70 |
classes for
|
|
71 |
the extended regular expressions.\footnote{Please call them
|
|
72 |
\code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES},
|
630
|
73 |
\code{UPTO}, \code{FROM} and \code{BETWEEN}.}
|
|
74 |
That means do not treat the extended regular expressions
|
567
|
75 |
by just translating them into the basic ones. See also Question 3,
|
|
76 |
where you are asked to explicitly give the rules for \textit{nullable}
|
748
|
77 |
and \textit{der} for the extended regular expressions. Something like
|
|
78 |
|
|
79 |
\[der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)\]
|
|
80 |
|
|
81 |
\noindent is \emph{not} allowed as answer in Question 3 and \emph{not}
|
|
82 |
allowed in your code.\medskip
|
492
|
83 |
|
|
84 |
\noindent
|
|
85 |
The meanings of the extended regular expressions are
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
|
492
|
89 |
$L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\
|
|
90 |
$L(r^+)$ & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\
|
|
91 |
$L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\
|
|
92 |
$L(r^{\{n\}})$ & $\dn$ & $L(r)^n$\\
|
|
93 |
$L(r^{\{..m\}})$ & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\
|
|
94 |
$L(r^{\{n..\}})$ & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\
|
|
95 |
$L(r^{\{n..m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\
|
|
96 |
$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
97 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
98 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
99 |
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
\noindent whereby in the last clause the set $\Sigma^*$ stands
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
for the set of \emph{all} strings over the alphabet $\Sigma$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
(in the implementation the alphabet can be just what is
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
represented by, say, the type \pcode{Char}). So $\sim{}r$
|
492
|
104 |
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
|
105 |
|
492
|
106 |
\noindent
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
Be careful that your implementation of \textit{nullable} and
|
492
|
108 |
\textit{der} satisfies for every regular expression $r$ the following
|
545
|
109 |
two properties (see also Question 3):
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
110 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
111 |
\begin{itemize}
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
\item $L(der\,c\,r) = Der\,c\,(L(r))$
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
114 |
\end{itemize}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
117 |
|
512
|
118 |
\subsection*{Question 1 (Unmarked)}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
119 |
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
What is your King's email address (you will need it in
|
545
|
121 |
Question 5)?
|
|
122 |
|
|
123 |
\subsection*{Question 2 (Unmarked)}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
|
567
|
125 |
Can you please list all programming languages in which you have
|
748
|
126 |
already written programs (include only instances where you have spent
|
|
127 |
at least a good working day fiddling with a program)? This is just
|
|
128 |
for my curiosity to estimate what your background is.
|
545
|
129 |
|
|
130 |
\subsection*{Question 3}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
|
473
|
132 |
From the
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
lectures you have seen the definitions for the functions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
\textit{nullable} and \textit{der} for the basic regular
|
718
|
135 |
expressions. Implement and write down the rules for the extended
|
567
|
136 |
regular expressions:
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
492
|
140 |
$\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\
|
|
141 |
$\textit{nullable}(r^+)$ & $\dn$ & $?$\\
|
|
142 |
$\textit{nullable}(r^?)$ & $\dn$ & $?$\\
|
|
143 |
$\textit{nullable}(r^{\{n\}})$ & $\dn$ & $?$\\
|
|
144 |
$\textit{nullable}(r^{\{..m\}})$ & $\dn$ & $?$\\
|
|
145 |
$\textit{nullable}(r^{\{n..\}})$ & $\dn$ & $?$\\
|
|
146 |
$\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & $?$\\
|
|
147 |
$\textit{nullable}(\sim{}r)$ & $\dn$ & $?$
|
|
148 |
\end{tabular}
|
|
149 |
\end{center}
|
|
150 |
|
|
151 |
\begin{center}
|
|
152 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
|
153 |
$der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\
|
|
154 |
$der\, c\, (r^+)$ & $\dn$ & $?$\\
|
|
155 |
$der\, c\, (r^?)$ & $\dn$ & $?$\\
|
|
156 |
$der\, c\, (r^{\{n\}})$ & $\dn$ & $?$\\
|
|
157 |
$der\, c\, (r^{\{..m\}})$ & $\dn$ & $?$\\
|
|
158 |
$der\, c\, (r^{\{n..\}})$ & $\dn$ & $?$\\
|
|
159 |
$der\, c\, (r^{\{n..m\}})$ & $\dn$ & $?$\\
|
|
160 |
$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
Remember your definitions have to satisfy the two properties
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
\begin{itemize}
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
\item $L(der\,c\,r)) = Der\,c\,(L(r))$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
|
473
|
172 |
\noindent
|
492
|
173 |
Given the definitions of \textit{nullable} and \textit{der}, it is
|
|
174 |
easy to implement a regular expression matcher. Test your regular
|
|
175 |
expression matcher with (at least) the examples:
|
|
176 |
|
|
177 |
|
|
178 |
\begin{center}
|
|
179 |
\def\arraystretch{1.2}
|
748
|
180 |
\begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}}
|
718
|
181 |
string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ &
|
|
182 |
$(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline
|
|
183 |
$[]$ &&&&&&& \\\hline
|
|
184 |
\texttt{a} &&&&&&& \\\hline
|
|
185 |
\texttt{aa} &&&&&&& \\\hline
|
|
186 |
\texttt{aaa} &&&&&&& \\\hline
|
|
187 |
\texttt{aaaaa} &&&&&&& \\\hline
|
|
188 |
\texttt{aaaaaa}&&&&&&& \\
|
492
|
189 |
\end{tabular}
|
|
190 |
\end{center}
|
|
191 |
|
|
192 |
\noindent
|
718
|
193 |
Does your matcher produce the expected results? Make sure you
|
|
194 |
also test corner-cases, like $a^{\{0\}}$!
|
473
|
195 |
|
545
|
196 |
\subsection*{Question 4}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
197 |
|
494
|
198 |
As you can see, there are a number of explicit regular expressions
|
|
199 |
that deal with single or several characters, for example:
|
492
|
200 |
|
|
201 |
\begin{center}
|
|
202 |
\begin{tabular}{ll}
|
494
|
203 |
$c$ & matches a single character\\
|
|
204 |
$[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\
|
|
205 |
$\textit{ALL}$ & matches any character
|
492
|
206 |
\end{tabular}
|
|
207 |
\end{center}
|
|
208 |
|
|
209 |
\noindent
|
567
|
210 |
The latter is useful for matching any string (for example
|
494
|
211 |
by using $\textit{ALL}^*$). In order to avoid having an explicit constructor
|
|
212 |
for each case, we can generalise all these cases and introduce a single
|
492
|
213 |
constructor $\textit{CFUN}(f)$ where $f$ is a function from characters
|
576
|
214 |
to booleans. In Scala code this would look as follows:
|
|
215 |
|
|
216 |
\begin{lstlisting}[numbers=none]
|
|
217 |
abstract class Rexp
|
|
218 |
...
|
|
219 |
case class CFUN(f: Char => Boolean) extends Rexp
|
|
220 |
\end{lstlisting}\smallskip
|
|
221 |
|
|
222 |
\noindent
|
|
223 |
The idea is that the function $f$ determines which character(s)
|
494
|
224 |
are matched, namely those where $f$ returns \texttt{true}.
|
|
225 |
In this question implement \textit{CFUN} and define
|
492
|
226 |
|
|
227 |
\begin{center}
|
|
228 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
|
229 |
$\textit{nullable}(\textit{CFUN}(f))$ & $\dn$ & $?$\\
|
|
230 |
$\textit{der}\,c\,(\textit{CFUN}(f))$ & $\dn$ & $?$
|
|
231 |
\end{tabular}
|
|
232 |
\end{center}
|
|
233 |
|
494
|
234 |
\noindent in your matcher and then also give definitions for
|
492
|
235 |
|
|
236 |
\begin{center}
|
|
237 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
|
238 |
$c$ & $\dn$ & $\textit{CFUN}(?)$\\
|
|
239 |
$[c_1,c_2,\ldots,c_n]$ & $\dn$ & $\textit{CFUN}(?)$\\
|
|
240 |
$\textit{ALL}$ & $\dn$ & $\textit{CFUN}(?)$
|
|
241 |
\end{tabular}
|
|
242 |
\end{center}
|
|
243 |
|
567
|
244 |
\noindent
|
|
245 |
You can either add the constructor $CFUN$ to your implementation in
|
|
246 |
Question 3, or you can implement this questions first
|
|
247 |
and then use $CFUN$ instead of \code{RANGE} and \code{CHAR} in Question 3.
|
|
248 |
|
492
|
249 |
|
545
|
250 |
\subsection*{Question 5}
|
492
|
251 |
|
|
252 |
Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression
|
|
253 |
|
|
254 |
\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\]
|
|
255 |
|
|
256 |
\noindent
|
|
257 |
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
|
258 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
259 |
\[
|
492
|
260 |
([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
|
261 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
262 |
|
567
|
263 |
\noindent and calculate the derivative according to your own email
|
395
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
address. When calculating the derivative, simplify all regular
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
265 |
expressions as much as possible by applying the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
following 7 simplification rules:
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
267 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
268 |
\begin{center}
|
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
269 |
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
|
439
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
270 |
$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
271 |
$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
272 |
$r \cdot \ONE$ & $\mapsto$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
273 |
$\ONE \cdot r$ & $\mapsto$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
274 |
$r + \ZERO$ & $\mapsto$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
275 |
$\ZERO + r$ & $\mapsto$ & $r$\\
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
276 |
$r + r$ & $\mapsto$ & $r$\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
277 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
278 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
279 |
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
280 |
\noindent Write down your simplified derivative in a readable
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
281 |
notation using parentheses where necessary. That means you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
282 |
should use the infix notation $+$, $\cdot$, $^*$ and so on,
|
567
|
283 |
instead of raw code.\bigskip
|
|
284 |
|
|
285 |
|
|
286 |
\subsection*{Question 6}
|
|
287 |
|
492
|
288 |
Implement the simplification rules in your regular expression matcher.
|
|
289 |
Consider the regular expression $/ \cdot * \cdot
|
|
290 |
(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *
|
630
|
291 |
\cdot /$ and decide whether the following four strings are matched by
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
292 |
this regular expression. Answer yes or no.
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
293 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
294 |
\begin{enumerate}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
295 |
\item \texttt{"/**/"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
296 |
\item \texttt{"/*foobar*/"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
297 |
\item \texttt{"/*test*/test*/"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
298 |
\item \texttt{"/*test/*test*/"}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
299 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
300 |
|
567
|
301 |
\subsection*{Question 7}
|
512
|
302 |
|
|
303 |
Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
|
748
|
304 |
$(a^{\{19,19\}}) \cdot (a^?)$.\medskip
|
|
305 |
|
|
306 |
\noindent
|
|
307 |
Decide whether the following three
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
strings consisting of $a$s only can be matched by $(r_1^+)^+$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
Similarly test them with $(r_2^+)^+$. Again answer in all six cases
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
310 |
with yes or no. \medskip
|
130
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
312 |
\noindent
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
313 |
These are strings are meant to be entirely made up of $a$s. Be careful
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
314 |
when copy-and-pasting the strings so as to not forgetting any $a$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
315 |
to not introducing any other character.
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
316 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
317 |
\begin{enumerate}
|
492
|
318 |
\setcounter{enumi}{4}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
320 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
321 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
322 |
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
323 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
325 |
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
326 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
328 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
329 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
330 |
|
492
|
331 |
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
332 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
333 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
334 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
335 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
336 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
337 |
%%% End:
|