| changeset 545 | 76a98ed71a2a |
| parent 512 | a6aa52ecc1c5 |
| child 556 | 40e22ad45744 |
| 544:748207ad3ef0 | 545:76a98ed71a2a |
|---|---|
63 |
63 |
64 \noindent {\bf Important!} Your implementation should have explicit |
64 \noindent {\bf Important!} Your implementation should have explicit |
65 cases for the basic regular expressions, but also for explicit cases for |
65 cases for the basic regular expressions, but also for explicit cases for |
66 the extended regular expressions. That means do not treat the extended |
66 the extended regular expressions. That means do not treat the extended |
67 regular expressions by just translating them into the basic ones. See |
67 regular expressions by just translating them into the basic ones. See |
68 also Question 2, where you are asked to explicitly give the rules for |
68 also Question 3, where you are asked to explicitly give the rules for |
69 \textit{nullable} and \textit{der} for the extended regular |
69 \textit{nullable} and \textit{der} for the extended regular |
70 expressions.\newpage |
70 expressions.\newpage |
71 |
71 |
72 \noindent |
72 \noindent |
73 The meanings of the extended regular expressions are |
73 The meanings of the extended regular expressions are |
92 means in effect ``all the strings that $r$ cannot match''.\medskip |
92 means in effect ``all the strings that $r$ cannot match''.\medskip |
93 |
93 |
94 \noindent |
94 \noindent |
95 Be careful that your implementation of \textit{nullable} and |
95 Be careful that your implementation of \textit{nullable} and |
96 \textit{der} satisfies for every regular expression $r$ the following |
96 \textit{der} satisfies for every regular expression $r$ the following |
97 two properties (see also Question 2): |
97 two properties (see also Question 3): |
98 |
98 |
99 \begin{itemize} |
99 \begin{itemize} |
100 \item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ |
100 \item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ |
101 \item $L(der\,c\,r) = Der\,c\,(L(r))$ |
101 \item $L(der\,c\,r) = Der\,c\,(L(r))$ |
102 \end{itemize} |
102 \end{itemize} |
104 |
104 |
105 |
105 |
106 \subsection*{Question 1 (Unmarked)} |
106 \subsection*{Question 1 (Unmarked)} |
107 |
107 |
108 What is your King's email address (you will need it in |
108 What is your King's email address (you will need it in |
109 Question 4)? |
109 Question 5)? |
110 |
110 |
111 \subsection*{Question 2} |
111 \subsection*{Question 2 (Unmarked)} |
112 |
|
113 In which programming languages have you written a program (like spent |
|
114 at least a day working on the program)? |
|
115 |
|
116 \subsection*{Question 3} |
|
112 |
117 |
113 From the |
118 From the |
114 lectures you have seen the definitions for the functions |
119 lectures you have seen the definitions for the functions |
115 \textit{nullable} and \textit{der} for the basic regular |
120 \textit{nullable} and \textit{der} for the basic regular |
116 expressions. Implement the rules for the extended regular |
121 expressions. Implement the rules for the extended regular |
171 \end{center} |
176 \end{center} |
172 |
177 |
173 \noindent |
178 \noindent |
174 Does your matcher produce the expected results? |
179 Does your matcher produce the expected results? |
175 |
180 |
176 \subsection*{Question 3} |
181 \subsection*{Question 4} |
177 |
182 |
178 As you can see, there are a number of explicit regular expressions |
183 As you can see, there are a number of explicit regular expressions |
179 that deal with single or several characters, for example: |
184 that deal with single or several characters, for example: |
180 |
185 |
181 \begin{center} |
186 \begin{center} |
211 $\textit{ALL}$ & $\dn$ & $\textit{CFUN}(?)$ |
216 $\textit{ALL}$ & $\dn$ & $\textit{CFUN}(?)$ |
212 \end{tabular} |
217 \end{tabular} |
213 \end{center} |
218 \end{center} |
214 |
219 |
215 |
220 |
216 \subsection*{Question 4} |
221 \subsection*{Question 5} |
217 |
222 |
218 Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression |
223 Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression |
219 |
224 |
220 \[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\] |
225 \[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\] |
221 |
226 |
260 \item \texttt{"/*foobar*/"} |
265 \item \texttt{"/*foobar*/"} |
261 \item \texttt{"/*test*/test*/"} |
266 \item \texttt{"/*test*/test*/"} |
262 \item \texttt{"/*test/*test*/"} |
267 \item \texttt{"/*test/*test*/"} |
263 \end{enumerate} |
268 \end{enumerate} |
264 |
269 |
265 \subsection*{Question 5} |
270 \subsection*{Question 6} |
266 |
271 |
267 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be |
272 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be |
268 $(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three |
273 $(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three |
269 strings consisting of $a$s only can be matched by $(r_1^+)^+$. |
274 strings consisting of $a$s only can be matched by $(r_1^+)^+$. |
270 Similarly test them with $(r_2^+)^+$. Again answer in all six cases |
275 Similarly test them with $(r_2^+)^+$. Again answer in all six cases |