7 |
7 |
8 |
8 |
9 \begin{document} |
9 \begin{document} |
10 \newcolumntype{C}[1]{>{\centering}m{#1}} |
10 \newcolumntype{C}[1]{>{\centering}m{#1}} |
11 |
11 |
12 \section*{Coursework 1 (Strand 1)} |
12 \section*{Coursework 1} |
13 |
13 |
14 This coursework is worth 4\% and is due on \cwONE{} at |
14 This coursework is worth 5\% and is due on \cwONE{} at 18:00. You are |
15 18:00. You are asked to implement a regular expression matcher |
15 asked to implement a regular expression matcher and submit a document |
16 and submit a document containing the answers for the questions |
16 containing the answers for the questions below. You can do the |
17 below. You can do the implementation in any programming |
17 implementation in any programming language you like, but you need to |
18 language you like, but you need to submit the source code with |
18 submit the source code with which you answered the questions, |
19 which you answered the questions, otherwise a mark of 0\% will |
19 otherwise a mark of 0\% will be awarded. You can submit your answers |
20 be awarded. You can submit your answers in a txt-file or pdf. |
20 in a txt-file or pdf. Code send as code. Please package everything |
21 Code send as code. |
21 inside a zip-file that creates a directory with the name |
|
22 \[\texttt{YournameYourfamilyname}\] |
|
23 |
|
24 \noindent on my end. Thanks! |
22 |
25 |
23 |
26 |
24 |
27 |
25 \subsubsection*{Disclaimer} |
28 \subsubsection*{Disclaimer} |
26 |
29 |
69 \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES}, |
72 \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES}, |
70 \code{UPTO}, \code{FROM} and \code{BETWEEN}.} |
73 \code{UPTO}, \code{FROM} and \code{BETWEEN}.} |
71 That means do not treat the extended regular expressions |
74 That means do not treat the extended regular expressions |
72 by just translating them into the basic ones. See also Question 3, |
75 by just translating them into the basic ones. See also Question 3, |
73 where you are asked to explicitly give the rules for \textit{nullable} |
76 where you are asked to explicitly give the rules for \textit{nullable} |
74 and \textit{der} for the extended regular expressions. So something like |
77 and \textit{der} for the extended regular expressions. Something like |
75 $der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)$ is \emph{not} allowed.\medskip |
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 |
76 |
83 |
77 \noindent |
84 \noindent |
78 The meanings of the extended regular expressions are |
85 The meanings of the extended regular expressions are |
79 |
86 |
80 \begin{center} |
87 \begin{center} |
114 Question 5)? |
121 Question 5)? |
115 |
122 |
116 \subsection*{Question 2 (Unmarked)} |
123 \subsection*{Question 2 (Unmarked)} |
117 |
124 |
118 Can you please list all programming languages in which you have |
125 Can you please list all programming languages in which you have |
119 already written programs (like spent at least a good working day |
126 already written programs (include only instances where you have spent |
120 fiddling with the program or programs)? This is just for my |
127 at least a good working day fiddling with a program)? This is just |
121 curiosity to estimate what your background is. |
128 for my curiosity to estimate what your background is. |
122 |
129 |
123 \subsection*{Question 3} |
130 \subsection*{Question 3} |
124 |
131 |
125 From the |
132 From the |
126 lectures you have seen the definitions for the functions |
133 lectures you have seen the definitions for the functions |
168 expression matcher with (at least) the examples: |
175 expression matcher with (at least) the examples: |
169 |
176 |
170 |
177 |
171 \begin{center} |
178 \begin{center} |
172 \def\arraystretch{1.2} |
179 \def\arraystretch{1.2} |
173 \begin{tabular}{@{}r|m{6mm}|m{6mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}|m{10mm}|m{10mm}} |
180 \begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}} |
174 string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ & |
181 string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ & |
175 $(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline |
182 $(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline |
176 $[]$ &&&&&&& \\\hline |
183 $[]$ &&&&&&& \\\hline |
177 \texttt{a} &&&&&&& \\\hline |
184 \texttt{a} &&&&&&& \\\hline |
178 \texttt{aa} &&&&&&& \\\hline |
185 \texttt{aa} &&&&&&& \\\hline |
292 \end{enumerate} |
299 \end{enumerate} |
293 |
300 |
294 \subsection*{Question 7} |
301 \subsection*{Question 7} |
295 |
302 |
296 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be |
303 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be |
297 $(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three |
304 $(a^{\{19,19\}}) \cdot (a^?)$.\medskip |
|
305 |
|
306 \noindent |
|
307 Decide whether the following three |
298 strings consisting of $a$s only can be matched by $(r_1^+)^+$. |
308 strings consisting of $a$s only can be matched by $(r_1^+)^+$. |
299 Similarly test them with $(r_2^+)^+$. Again answer in all six cases |
309 Similarly test them with $(r_2^+)^+$. Again answer in all six cases |
300 with yes or no. \medskip |
310 with yes or no. \medskip |
301 |
311 |
302 \noindent |
312 \noindent |