15 according to the answers. You can submit your answers in a txt-file or |
15 according to the answers. You can submit your answers in a txt-file or |
16 pdf. |
16 pdf. |
17 |
17 |
18 \subsubsection*{Disclaimer} |
18 \subsubsection*{Disclaimer} |
19 |
19 |
20 It should be understood that the work submitted represents your own effort. |
20 It should be understood that the work you submit represents your own |
21 You have not copied from anyone else. An exception is the Scala code I |
21 effort. You have not copied from anyone else. An exception is the |
22 showed during the lectures, which you can use.\bigskip |
22 Scala code I showed during the lectures, which you can use.\bigskip |
23 |
23 |
24 |
24 |
25 \subsubsection*{Tasks} |
25 \subsubsection*{Tasks} |
26 |
26 |
27 The task is to implement a regular expression matcher based on |
27 The task is to implement a regular expression matcher based on |
60 \end{center} |
60 \end{center} |
61 |
61 |
62 \noindent |
62 \noindent |
63 whereby in the last clause the set $\mathbb{A}$ stands for the set of |
63 whereby in the last clause the set $\mathbb{A}$ stands for the set of |
64 \emph{all} strings. So $\sim{}r$ means `all the strings that $r$ |
64 \emph{all} strings. So $\sim{}r$ means `all the strings that $r$ |
65 cannot match'. We assume ranges like $[a\mbox{-}z0\mbox{-}9]$ are a |
65 cannot match'. |
66 shorthand for the regular expression |
|
67 |
66 |
68 \[ |
|
69 [a b c d\ldots z 0 1\ldots 9]\;. |
|
70 \] |
|
71 |
|
72 \noindent |
|
73 Be careful that your implementation of $nullable$ and $der$ satisfies |
67 Be careful that your implementation of $nullable$ and $der$ satisfies |
74 for every $r$ the following two properties: |
68 for every $r$ the following two properties (see also Question 2): |
75 |
69 |
76 \begin{itemize} |
70 \begin{itemize} |
77 \item $nullable(r)$ if and only if $[]\in L(r)$ |
71 \item $nullable(r)$ if and only if $[]\in L(r)$ |
78 \item $L(der\,c\,r)) = Der\,c\,(L(r))$ |
72 \item $L(der\,c\,r)) = Der\,c\,(L(r))$ |
79 \end{itemize} |
73 \end{itemize} |
80 |
74 |
81 \noindent |
75 \noindent |
82 {\bf Important!} Your implementation should have explicit cases for the |
76 {\bf Important!} Your implementation should have explicit cases for |
83 basic regular expressions, but also for the extended regular expressions. |
77 the basic regular expressions, but also explicit cases for the |
84 That means do not treat the extended regular expressions by just translating |
78 extended regular expressions. That means do not treat the extended |
85 them into the basic ones. See also Question 2, where you asked to give |
79 regular expressions by just translating them into the basic ones. See |
86 the rules for \textit{nullable} and \textit{der}. |
80 also Question 2, where you are asked to explicitly give the rules for |
|
81 \textit{nullable} and \textit{der} for the extended regular |
|
82 expressions. |
87 |
83 |
88 |
84 |
89 \subsection*{Question 1 (unmarked)} |
85 \subsection*{Question 1 (unmarked)} |
90 |
86 |
91 What is your King's email address (you will need it in Question 2)? |
87 What is your King's email address (you will need it in Question 2)? |
92 |
88 |
93 \subsection*{Question 2 (marked with 2\%)} |
89 \subsection*{Question 2 (marked with 2\%)} |
94 |
90 |
95 This question does not require any implementation. From the lectures |
91 This question does not require any implementation. From the lectures |
96 you have seen the definitions for the functions \textit{nullable} and |
92 you have seen the definitions for the functions \textit{nullable} and |
97 \textit{der}. Give the rules for the extended regular expressions: |
93 \textit{der} for the basic regular expressions. Give the rules for |
|
94 the extended regular expressions: |
98 |
95 |
99 \begin{center} |
96 \begin{center} |
100 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
97 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
101 $nullable([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ |
98 $nullable([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ |
102 $nullable(r^+)$ & $\dn$ & $?$\\ |
99 $nullable(r^+)$ & $\dn$ & $?$\\ |
103 $nullable(r^?)$ & $\dn$ & $?$\\ |
100 $nullable(r^?)$ & $\dn$ & $?$\\ |
104 $nullable(r^{\{n,m\}})$ & $\dn$ & $?$\\ |
101 $nullable(r^{\{n,m\}})$ & $\dn$ & $?$\\ |
105 $nullable(\sim{}r)$ & $\dn$ & $?$\medskip\\ |
102 $nullable(\sim{}r)$ & $\dn$ & $?$\medskip\\ |
106 $der c ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ |
103 $der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ |
107 $der c (r^+)$ & $\dn$ & $?$\\ |
104 $der\, c\, (r^+)$ & $\dn$ & $?$\\ |
108 $der c (r^?)$ & $\dn$ & $?$\\ |
105 $der\, c\, (r^?)$ & $\dn$ & $?$\\ |
109 $der c (r^{\{n,m\}})$ & $\dn$ & $?$\\ |
106 $der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\ |
110 $der c (\sim{}r)$ & $\dn$ & $?$\\ |
107 $der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ |
111 \end{tabular} |
108 \end{tabular} |
112 \end{center} |
109 \end{center} |
113 |
110 |
114 \subsection*{Question 3 (marked with 1\%)} |
111 \subsection*{Question 3 (marked with 1\%)} |
115 |
112 |
140 Write down your simplified derivative in the ``mathematicical'' |
137 Write down your simplified derivative in the ``mathematicical'' |
141 notation using parentheses where necessary. |
138 notation using parentheses where necessary. |
142 |
139 |
143 \subsection*{Question 4 (marked with 1\%)} |
140 \subsection*{Question 4 (marked with 1\%)} |
144 |
141 |
145 Consider the regular expression $/ \cdot * \cdot |
142 Suppose \textit{[a-z]} stands for the range regular expression |
|
143 $[a,b,c,\ldots,z]$. Consider the regular expression $/ \cdot * \cdot |
146 (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * |
144 (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * |
147 \cdot /$ and decide wether the following four strings are matched by |
145 \cdot /$ and decide wether the following four strings are matched by |
148 this regular expression. Answer yes or no. |
146 this regular expression. Answer yes or no. |
149 |
147 |
150 \begin{enumerate} |
148 \begin{enumerate} |