55 \begin{center} |
55 \begin{center} |
56 \begin{tabular}{ll} |
56 \begin{tabular}{ll} |
57 $[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\ |
57 $[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\ |
58 $r^+$ & one or more times $r$\\ |
58 $r^+$ & one or more times $r$\\ |
59 $r^?$ & optional $r$\\ |
59 $r^?$ & optional $r$\\ |
|
60 $r_1 \,\&\, r_2$ & intersection (matched by both $r_1$ and $r_2$)\\ |
60 $r^{\{n\}}$ & exactly $n$-times\\ |
61 $r^{\{n\}}$ & exactly $n$-times\\ |
61 $r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\ |
62 $r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\ |
62 $r^{\{n..\}}$ & at least $n$-times $r$\\ |
63 $r^{\{n..\}}$ & at least $n$-times $r$\\ |
63 $r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\ |
64 $r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\ |
64 $\sim{}r$ & not-regular-expression of $r$\\ |
65 $\sim{}r$ & not-regular-expression of $r$\\ |
70 |
71 |
71 \noindent {\bf Important!} Your implementation should have explicit |
72 \noindent {\bf Important!} Your implementation should have explicit |
72 case classes for the basic regular expressions, but also explicit case |
73 case classes for the basic regular expressions, but also explicit case |
73 classes for |
74 classes for |
74 the extended regular expressions.\footnote{Please call them |
75 the extended regular expressions.\footnote{Please call them |
75 \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES}, |
76 \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{AND}, \code{NTIMES}, |
76 \code{UPTO}, \code{FROM} and \code{BETWEEN}.} |
77 \code{UPTO}, \code{FROM} and \code{BETWEEN}.} |
77 That means do not treat the extended regular expressions |
78 That means do not treat the extended regular expressions |
78 by just translating them into the basic ones. See also Question 3, |
79 by just translating them into the basic ones. See also Question 3, |
79 where you are asked to explicitly give the rules for \textit{nullable} |
80 where you are asked to explicitly give the rules for \textit{nullable} |
80 and \textit{der} for the extended regular expressions. Something like |
81 and \textit{der} for the extended regular expressions. Something like |
90 \begin{center} |
91 \begin{center} |
91 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} |
92 \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} |
92 $L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ |
93 $L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ |
93 $L(r^+)$ & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\ |
94 $L(r^+)$ & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\ |
94 $L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ |
95 $L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ |
|
96 $L(r_1 \,\&\, r_2)$ & $\dn$ & $L(r_1) \cap L(r_2)$\\ |
95 $L(r^{\{n\}})$ & $\dn$ & $L(r)^n$\\ |
97 $L(r^{\{n\}})$ & $\dn$ & $L(r)^n$\\ |
96 $L(r^{\{..m\}})$ & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\ |
98 $L(r^{\{..m\}})$ & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\ |
97 $L(r^{\{n..\}})$ & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\ |
99 $L(r^{\{n..\}})$ & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\ |
98 $L(r^{\{n..m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\ |
100 $L(r^{\{n..m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\ |
99 $L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ |
101 $L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$ |
119 |
121 |
120 |
122 |
121 \subsection*{Question 1 (Unmarked)} |
123 \subsection*{Question 1 (Unmarked)} |
122 |
124 |
123 What is your King's email address (you will need it in |
125 What is your King's email address (you will need it in |
124 Question 5)? Also could you please let me know from where you will be mainly |
126 Question 5)? Also could you please let me know whether you are |
125 studying? (online / in-person, in London / somewhere else) Thanks! |
127 a BSc / MSci and the year you are in (in case of MSci). Thanks! |
|
128 |
126 |
129 |
127 \subsection*{Question 2 (Unmarked)} |
130 \subsection*{Question 2 (Unmarked)} |
128 |
131 |
129 Can you please also list all programming languages in which you have |
132 Can you please also list all programming languages in which you have |
130 already written programs (include only instances where you have spent |
133 already written programs (include only instances where you have spent |
134 \subsection*{Question 3} |
137 \subsection*{Question 3} |
135 |
138 |
136 From the |
139 From the |
137 lectures you have seen the definitions for the functions |
140 lectures you have seen the definitions for the functions |
138 \textit{nullable} and \textit{der} for the basic regular |
141 \textit{nullable} and \textit{der} for the basic regular |
139 expressions. Implement and write down the rules for the extended |
142 expressions. Implement and \underline{write down} the rules for the extended |
140 regular expressions: |
143 regular expressions: |
141 |
144 |
142 \begin{center} |
145 \begin{center} |
143 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
146 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
144 $\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
147 $\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
145 $\textit{nullable}(r^+)$ & $\dn$ & $?$\\ |
148 $\textit{nullable}(r^+)$ & $\dn$ & $?$\\ |
146 $\textit{nullable}(r^?)$ & $\dn$ & $?$\\ |
149 $\textit{nullable}(r^?)$ & $\dn$ & $?$\\ |
|
150 $\textit{nullable}(r_1 \,\&\, r_2)$ & $\dn$ & $?$\\ |
147 $\textit{nullable}(r^{\{n\}})$ & $\dn$ & $?$\\ |
151 $\textit{nullable}(r^{\{n\}})$ & $\dn$ & $?$\\ |
148 $\textit{nullable}(r^{\{..m\}})$ & $\dn$ & $?$\\ |
152 $\textit{nullable}(r^{\{..m\}})$ & $\dn$ & $?$\\ |
149 $\textit{nullable}(r^{\{n..\}})$ & $\dn$ & $?$\\ |
153 $\textit{nullable}(r^{\{n..\}})$ & $\dn$ & $?$\\ |
150 $\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & $?$\\ |
154 $\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & $?$\\ |
151 $\textit{nullable}(\sim{}r)$ & $\dn$ & $?$ |
155 $\textit{nullable}(\sim{}r)$ & $\dn$ & $?$ |
155 \begin{center} |
159 \begin{center} |
156 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
160 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
157 $der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
161 $der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
158 $der\, c\, (r^+)$ & $\dn$ & $?$\\ |
162 $der\, c\, (r^+)$ & $\dn$ & $?$\\ |
159 $der\, c\, (r^?)$ & $\dn$ & $?$\\ |
163 $der\, c\, (r^?)$ & $\dn$ & $?$\\ |
|
164 $der\, c\, (r_1 \,\&\, r_2)$ & $\dn$ & $?$\\ |
160 $der\, c\, (r^{\{n\}})$ & $\dn$ & $?$\\ |
165 $der\, c\, (r^{\{n\}})$ & $\dn$ & $?$\\ |
161 $der\, c\, (r^{\{..m\}})$ & $\dn$ & $?$\\ |
166 $der\, c\, (r^{\{..m\}})$ & $\dn$ & $?$\\ |
162 $der\, c\, (r^{\{n..\}})$ & $\dn$ & $?$\\ |
167 $der\, c\, (r^{\{n..\}})$ & $\dn$ & $?$\\ |
163 $der\, c\, (r^{\{n..m\}})$ & $\dn$ & $?$\\ |
168 $der\, c\, (r^{\{n..m\}})$ & $\dn$ & $?$\\ |
164 $der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ |
169 $der\, c\, (\sim{}r)$ & $\dn$ & $?$\\ |
174 \end{itemize} |
179 \end{itemize} |
175 |
180 |
176 \noindent |
181 \noindent |
177 Given the definitions of \textit{nullable} and \textit{der}, it is |
182 Given the definitions of \textit{nullable} and \textit{der}, it is |
178 easy to implement a regular expression matcher. Test your regular |
183 easy to implement a regular expression matcher. Test your regular |
179 expression matcher with (at least) the examples: |
184 expression matcher with (\underline{at least}) the examples: |
180 |
185 |
181 |
186 |
182 \begin{center} |
187 \begin{center} |
183 \def\arraystretch{1.2} |
188 \def\arraystretch{1.2} |
184 \begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}} |
189 \begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}} |