15 This coursework is worth 5\% and is due on \cwONE{} at 16:00. You are |
16 This coursework is worth 5\% and is due on \cwONE{} at 16:00. You are |
16 asked to implement a regular expression matcher and submit a document |
17 asked to implement a regular expression matcher and submit a document |
17 containing the answers for the questions below. You can do the |
18 containing the answers for the questions below. You can do the |
18 implementation in any programming language you like, but you need to |
19 implementation in any programming language you like, but you need to |
19 submit the source code with which you answered the questions, |
20 submit the source code with which you answered the questions, |
20 otherwise a mark of 0\% will be awarded. You can submit your answers |
21 otherwise a mark of 0\% will be awarded. You need to submit your written |
21 in a txt-file or pdf. Code send as code. Please package everything |
22 answers as pdf---see attached questionaire. Code send as code. If you use |
22 inside a zip-file that creates a directory with the name |
23 Scala in your code, a good place to start is the file \texttt{re3.sc} |
23 \[\texttt{YournameYourfamilyname}\] |
24 that is uploaded to Github. |
24 |
25 |
25 \noindent on my end. Thanks! |
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! |
26 |
31 |
27 |
32 |
28 |
33 |
29 \subsubsection*{Disclaimer\alert} |
34 \subsubsection*{Disclaimer\alert} |
30 |
35 |
31 It should be understood that the work you submit represents |
36 It should be understood that the work you submit represents |
32 your \textbf{own} effort. You have not copied from anyone else. An |
37 your \textbf{own} effort. You have not copied from anyone else |
|
38 including CoPilot, ChatGPT \& Co. An |
33 exception is the Scala code I showed during the lectures or |
39 exception is the Scala code I showed during the lectures or |
34 uploaded to KEATS, which you can freely use. Do not |
40 uploaded to KEATS, which you can freely use. Do not |
35 be tempted to ask Github Copilot for help or do any other |
41 be tempted to ask Github Copilot for help or do any other |
36 shenanigans like this!\bigskip |
42 shenanigans like this!\bigskip |
37 |
43 |
38 \noindent |
44 \noindent |
39 If you have any questions, please send me an email in \textbf{good} |
45 If you have any questions, please send me an email in \textbf{good} |
40 time.\bigskip |
46 time!\bigskip |
41 |
47 |
42 \subsection*{Task} |
48 \subsection*{Task} |
43 |
49 |
44 The task is to implement a regular expression matcher based on |
50 The task is to implement a regular expression matcher based on |
45 derivatives of regular expressions. The implementation should |
51 derivatives of regular expressions. The implementation should |
134 at least a good working day fiddling with a program)? This is just |
140 at least a good working day fiddling with a program)? This is just |
135 for my curiosity to estimate what your background is. |
141 for my curiosity to estimate what your background is. |
136 |
142 |
137 \subsection*{Question 3} |
143 \subsection*{Question 3} |
138 |
144 |
139 From the |
145 From the lectures you have seen the definitions for the functions |
140 lectures you have seen the definitions for the functions |
|
141 \textit{nullable} and \textit{der} for the basic regular |
146 \textit{nullable} and \textit{der} for the basic regular |
142 expressions. Implement and \underline{write down} the rules for the extended |
147 expressions. Implement and \underline{write down} the rules for the |
143 regular expressions: |
148 extended regular expressions (see questionaire at the end). |
144 |
149 |
145 \begin{center} |
|
146 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
147 $\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
|
148 $\textit{nullable}(r^+)$ & $\dn$ & $?$\\ |
|
149 $\textit{nullable}(r^?)$ & $\dn$ & $?$\\ |
|
150 $\textit{nullable}(r_1 \,\&\, r_2)$ & $\dn$ & $?$\\ |
|
151 $\textit{nullable}(r^{\{n\}})$ & $\dn$ & $?$\\ |
|
152 $\textit{nullable}(r^{\{..m\}})$ & $\dn$ & $?$\\ |
|
153 $\textit{nullable}(r^{\{n..\}})$ & $\dn$ & $?$\\ |
|
154 $\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & $?$\\ |
|
155 $\textit{nullable}(\sim{}r)$ & $\dn$ & $?$ |
|
156 \end{tabular} |
|
157 \end{center} |
|
158 |
|
159 \begin{center} |
|
160 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
161 $der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
|
162 $der\, c\, (r^+)$ & $\dn$ & $?$\\ |
|
163 $der\, c\, (r^?)$ & $\dn$ & $?$\\ |
|
164 $der\, c\, (r_1 \,\&\, r_2)$ & $\dn$ & $?$\\ |
|
165 $der\, c\, (r^{\{n\}})$ & $\dn$ & $?$\\ |
|
166 $der\, c\, (r^{\{..m\}})$ & $\dn$ & $?$\\ |
|
167 $der\, c\, (r^{\{n..\}})$ & $\dn$ & $?$\\ |
|
168 $der\, c\, (r^{\{n..m\}})$ & $\dn$ & $?$\\ |
|
169 $der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ |
|
170 \end{tabular} |
|
171 \end{center} |
|
172 |
150 |
173 \noindent |
151 \noindent |
174 Remember your definitions have to satisfy the two properties |
152 Remember your definitions have to satisfy the two properties |
175 |
153 |
176 \begin{itemize} |
154 \begin{itemize} |
323 These are strings are meant to be entirely made up of $a$s. Be careful |
301 These are strings are meant to be entirely made up of $a$s. Be careful |
324 when copy-and-pasting the strings so as to not forgetting any $a$ and |
302 when copy-and-pasting the strings so as to not forgetting any $a$ and |
325 to not introducing any other character. |
303 to not introducing any other character. |
326 |
304 |
327 \begin{enumerate} |
305 \begin{enumerate} |
328 \setcounter{enumi}{4} |
306 \setcounter{enumi}{0} |
329 \item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
307 \item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
330 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
308 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
331 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} |
309 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} |
332 \item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
310 \item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
333 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
311 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
335 \item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
313 \item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
336 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
314 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
337 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} |
315 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"} |
338 \end{enumerate} |
316 \end{enumerate} |
339 |
317 |
340 |
318 \newpage |
|
319 \section*{Answers} |
|
320 |
|
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} |
341 |
439 |
342 \end{document} |
440 \end{document} |
343 |
441 |
344 %%% Local Variables: |
442 %%% Local Variables: |
345 %%% mode: latex |
443 %%% mode: latex |