1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
2 \usepackage{../style} |
3 \usepackage{../langs} |
3 \usepackage{../langs} |
4 \usepackage{../graphics} |
4 \usepackage{disclaimer} |
|
5 \usepackage{tikz} |
|
6 \usepackage{pgf} |
|
7 \usepackage{pgfplots} |
|
8 \usepackage{stackengine} |
|
9 %% \usepackage{accents} |
|
10 \newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}} |
|
11 |
|
12 \begin{filecontents}{re-python2.data} |
|
13 1 0.033 |
|
14 5 0.036 |
|
15 10 0.034 |
|
16 15 0.036 |
|
17 18 0.059 |
|
18 19 0.084 |
|
19 20 0.141 |
|
20 21 0.248 |
|
21 22 0.485 |
|
22 23 0.878 |
|
23 24 1.71 |
|
24 25 3.40 |
|
25 26 7.08 |
|
26 27 14.12 |
|
27 28 26.69 |
|
28 \end{filecontents} |
|
29 |
|
30 \begin{filecontents}{re-java.data} |
|
31 5 0.00298 |
|
32 10 0.00418 |
|
33 15 0.00996 |
|
34 16 0.01710 |
|
35 17 0.03492 |
|
36 18 0.03303 |
|
37 19 0.05084 |
|
38 20 0.10177 |
|
39 21 0.19960 |
|
40 22 0.41159 |
|
41 23 0.82234 |
|
42 24 1.70251 |
|
43 25 3.36112 |
|
44 26 6.63998 |
|
45 27 13.35120 |
|
46 28 29.81185 |
|
47 \end{filecontents} |
|
48 |
|
49 \begin{filecontents}{re-js.data} |
|
50 5 0.061 |
|
51 10 0.061 |
|
52 15 0.061 |
|
53 20 0.070 |
|
54 23 0.131 |
|
55 25 0.308 |
|
56 26 0.564 |
|
57 28 1.994 |
|
58 30 7.648 |
|
59 31 15.881 |
|
60 32 32.190 |
|
61 \end{filecontents} |
|
62 |
|
63 \begin{filecontents}{re-java9.data} |
|
64 1000 0.01410 |
|
65 2000 0.04882 |
|
66 3000 0.10609 |
|
67 4000 0.17456 |
|
68 5000 0.27530 |
|
69 6000 0.41116 |
|
70 7000 0.53741 |
|
71 8000 0.70261 |
|
72 9000 0.93981 |
|
73 10000 0.97419 |
|
74 11000 1.28697 |
|
75 12000 1.51387 |
|
76 14000 2.07079 |
|
77 16000 2.69846 |
|
78 20000 4.41823 |
|
79 24000 6.46077 |
|
80 26000 7.64373 |
|
81 30000 9.99446 |
|
82 34000 12.966885 |
|
83 38000 16.281621 |
|
84 42000 19.180228 |
|
85 46000 21.984721 |
|
86 50000 26.950203 |
|
87 60000 43.0327746 |
|
88 \end{filecontents} |
|
89 |
5 |
90 |
6 \begin{document} |
91 \begin{document} |
7 |
92 |
8 \section*{Replacement Coursework 2 (Automata)} |
93 % BF IDE |
9 |
94 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5 |
10 This coursework is worth 10\%. It is about deterministic and |
95 |
11 non-deterministic finite automata. The coursework is due on 21 March |
96 \section*{Coursework 9 (Scala)} |
12 at 5pm. Make sure the files you submit can be processed by just |
97 |
13 calling \texttt{scala <<filename.scala>>}.\bigskip |
98 This coursework is worth 10\%. It is about a regular expression |
|
99 matcher and the shunting yard algorithm by Dijkstra. The first part is |
|
100 due on 6 December at 11pm; the second, more advanced part, is due on |
|
101 21 December at 11pm. In the first part, you are asked to implement a |
|
102 regular expression matcher based on derivatives of regular |
|
103 expressions. The reason is that regular expression matching in |
|
104 languages like Java, JavaScipt and Python can sometimes be extremely |
|
105 slow. The advanced part is about the shunting yard algorithm that |
|
106 transforms the usual infix notation of arithmetic expressions into the |
|
107 postfix notation, which is for example used in compilers.\bigskip |
|
108 |
|
109 \IMPORTANT{} |
14 |
110 |
15 \noindent |
111 \noindent |
16 \textbf{Important:} Do not use any mutable data structures in your |
112 Also note that the running time of each part will be restricted to a |
17 submission! They are not needed. This means you cannot use |
113 maximum of 30 seconds on my laptop. |
18 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
114 |
19 code! It has a different meaning in Scala, than in Java. Do not use |
115 \DISCLAIMER{} |
20 \texttt{var}! This declares a mutable variable. Make sure the |
116 |
21 functions you submit are defined on the ``top-level'' of Scala, not |
117 |
22 inside a class or object. Also note that when marking, the running time |
118 \subsection*{Part 1 (6 Marks, Regular Expression Matcher)} |
23 will be restricted to a maximum of 360 seconds on my laptop. |
119 |
24 |
120 The task is to implement a regular expression matcher that is based on |
25 |
121 derivatives of regular expressions. Most of the functions are defined by |
26 \subsection*{Disclaimer} |
122 recursion over regular expressions and can be elegantly implemented |
27 |
123 using Scala's pattern-matching. The implementation should deal with the |
28 It should be understood that the work you submit represents your own |
124 following regular expressions, which have been predefined in the file |
29 effort! You have not copied from anyone else. An exception is the |
125 \texttt{re.scala}: |
30 Scala code I showed during the lectures or uploaded to KEATS, which |
126 |
31 you can freely use.\bigskip |
127 \begin{center} |
32 |
128 \begin{tabular}{lcll} |
33 |
129 $r$ & $::=$ & $\ZERO$ & cannot match anything\\ |
34 \subsection*{Part 1 (Deterministic Finite Automata)} |
130 & $|$ & $\ONE$ & can only match the empty string\\ |
|
131 & $|$ & $c$ & can match a single character (in this case $c$)\\ |
|
132 & $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\ |
|
133 & $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\ |
|
134 & & & then the second part with $r_2$\\ |
|
135 & $|$ & $r^*$ & can match a string with zero or more copies of $r$\\ |
|
136 \end{tabular} |
|
137 \end{center} |
|
138 |
|
139 \noindent |
|
140 Why? Knowing how to match regular expressions and strings will let you |
|
141 solve a lot of problems that vex other humans. Regular expressions are |
|
142 one of the fastest and simplest ways to match patterns in text, and |
|
143 are endlessly useful for searching, editing and analysing data in all |
|
144 sorts of places (for example analysing network traffic in order to |
|
145 detect security breaches). However, you need to be fast, otherwise you |
|
146 will stumble over problems such as recently reported at |
|
147 |
|
148 {\small |
|
149 \begin{itemize} |
|
150 \item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} |
|
151 \item[$\bullet$] \url{https://vimeo.com/112065252} |
|
152 \item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/} |
|
153 \end{itemize}} |
|
154 |
|
155 \subsubsection*{Tasks (file re.scala)} |
|
156 |
|
157 The file \texttt{re.scala} has already a definition for regular |
|
158 expressions and also defines some handy shorthand notation for |
|
159 regular expressions. The notation in this document matches up |
|
160 with the code in the file as follows: |
|
161 |
|
162 \begin{center} |
|
163 \begin{tabular}{rcl@{\hspace{10mm}}l} |
|
164 & & code: & shorthand:\smallskip \\ |
|
165 $\ZERO$ & $\mapsto$ & \texttt{ZERO}\\ |
|
166 $\ONE$ & $\mapsto$ & \texttt{ONE}\\ |
|
167 $c$ & $\mapsto$ & \texttt{CHAR(c)}\\ |
|
168 $r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\ |
|
169 $r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\ |
|
170 $r^*$ & $\mapsto$ & \texttt{STAR(r)} & \texttt{r.\%} |
|
171 \end{tabular} |
|
172 \end{center} |
|
173 |
|
174 |
|
175 \begin{itemize} |
|
176 \item[(1)] Implement a function, called \textit{nullable}, by |
|
177 recursion over regular expressions. This function tests whether a |
|
178 regular expression can match the empty string. This means given a |
|
179 regular expression it either returns true or false. The function |
|
180 \textit{nullable} |
|
181 is defined as follows: |
|
182 |
|
183 \begin{center} |
|
184 \begin{tabular}{lcl} |
|
185 $\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\ |
|
186 $\textit{nullable}(\ONE)$ & $\dn$ & $\textit{true}$\\ |
|
187 $\textit{nullable}(c)$ & $\dn$ & $\textit{false}$\\ |
|
188 $\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\ |
|
189 $\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\ |
|
190 $\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\ |
|
191 \end{tabular} |
|
192 \end{center}~\hfill[1 Mark] |
|
193 |
|
194 \item[(2)] Implement a function, called \textit{der}, by recursion over |
|
195 regular expressions. It takes a character and a regular expression |
|
196 as arguments and calculates the derivative regular expression according |
|
197 to the rules: |
|
198 |
|
199 \begin{center} |
|
200 \begin{tabular}{lcl} |
|
201 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\ |
|
202 $\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\ |
|
203 $\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\ |
|
204 $\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\ |
|
205 $\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\ |
|
206 & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\ |
|
207 & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\ |
|
208 $\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\ |
|
209 \end{tabular} |
|
210 \end{center} |
|
211 |
|
212 For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives |
|
213 w.r.t.~the characters $a$, $b$ and $c$ are |
|
214 |
|
215 \begin{center} |
|
216 \begin{tabular}{lcll} |
|
217 $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & \quad($= r'$)\\ |
|
218 $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\ |
|
219 $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$ |
|
220 \end{tabular} |
|
221 \end{center} |
|
222 |
|
223 Let $r'$ stand for the first derivative, then taking the derivatives of $r'$ |
|
224 w.r.t.~the characters $a$, $b$ and $c$ gives |
|
225 |
|
226 \begin{center} |
|
227 \begin{tabular}{lcll} |
|
228 $\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\ |
|
229 $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & \quad($= r''$)\\ |
|
230 $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ |
|
231 \end{tabular} |
|
232 \end{center} |
|
233 |
|
234 One more example: Let $r''$ stand for the second derivative above, |
|
235 then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$ |
|
236 and $c$ gives |
|
237 |
|
238 \begin{center} |
|
239 \begin{tabular}{lcll} |
|
240 $\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\ |
|
241 $\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\ |
|
242 $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ & |
|
243 (is $\textit{nullable}$) |
|
244 \end{tabular} |
|
245 \end{center} |
|
246 |
|
247 Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\ |
|
248 \mbox{}\hfill\mbox{[1 Mark]} |
|
249 |
|
250 \item[(3)] Implement the function \textit{simp}, which recursively |
|
251 traverses a regular expression from the inside to the outside, and |
|
252 on the way simplifies every regular expression on the left (see |
|
253 below) to the regular expression on the right, except it does not |
|
254 simplify inside ${}^*$-regular expressions. |
|
255 |
|
256 \begin{center} |
|
257 \begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll} |
|
258 $r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ |
|
259 $\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ |
|
260 $r \cdot \ONE$ & $\mapsto$ & $r$\\ |
|
261 $\ONE \cdot r$ & $\mapsto$ & $r$\\ |
|
262 $r + \ZERO$ & $\mapsto$ & $r$\\ |
|
263 $\ZERO + r$ & $\mapsto$ & $r$\\ |
|
264 $r + r$ & $\mapsto$ & $r$\\ |
|
265 \end{tabular} |
|
266 \end{center} |
|
267 |
|
268 For example the regular expression |
|
269 \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] |
|
270 |
|
271 simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be |
|
272 seen as trees and there are several methods for traversing |
|
273 trees. One of them corresponds to the inside-out traversal, which is |
|
274 sometimes also called post-order traversal'' you traverse inside the |
|
275 tree and on the way up, you apply simplification rules. |
|
276 Furthermore, |
|
277 remember numerical expressions from school times: there you had expressions |
|
278 like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$ |
|
279 and simplification rules that looked very similar to rules |
|
280 above. You would simplify such numerical expressions by replacing |
|
281 for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then |
|
282 look whether more rules are applicable. If you organise the |
|
283 simplification in an inside-out fashion, it is always clear which |
|
284 rule should be applied next.\hfill[1 Mark] |
|
285 |
|
286 \item[(4)] Implement two functions: The first, called \textit{ders}, |
|
287 takes a list of characters and a regular expression as arguments, and |
|
288 builds the derivative w.r.t.~the list as follows: |
|
289 |
|
290 \begin{center} |
|
291 \begin{tabular}{lcl} |
|
292 $\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\ |
|
293 $\textit{ders}\;(c::cs)\;r$ & $\dn$ & |
|
294 $\textit{ders}\;cs\;(\textit{simp}(\textit{der}\;c\;r))$\\ |
|
295 \end{tabular} |
|
296 \end{center} |
|
297 |
|
298 Note that this function is different from \textit{der}, which only |
|
299 takes a single character. |
|
300 |
|
301 The second function, called \textit{matcher}, takes a string and a |
|
302 regular expression as arguments. It builds first the derivatives |
|
303 according to \textit{ders} and after that tests whether the resulting |
|
304 derivative regular expression can match the empty string (using |
|
305 \textit{nullable}). For example the \textit{matcher} will produce |
|
306 true for the regular expression $(a\cdot b)\cdot c$ and the string |
|
307 $abc$, but false if you give it the string $ab$. \hfill[1 Mark] |
|
308 |
|
309 \item[(5)] Implement a function, called \textit{size}, by recursion |
|
310 over regular expressions. If a regular expression is seen as a tree, |
|
311 then \textit{size} should return the number of nodes in such a |
|
312 tree. Therefore this function is defined as follows: |
|
313 |
|
314 \begin{center} |
|
315 \begin{tabular}{lcl} |
|
316 $\textit{size}(\ZERO)$ & $\dn$ & $1$\\ |
|
317 $\textit{size}(\ONE)$ & $\dn$ & $1$\\ |
|
318 $\textit{size}(c)$ & $\dn$ & $1$\\ |
|
319 $\textit{size}(r_1 + r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\ |
|
320 $\textit{size}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\ |
|
321 $\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\ |
|
322 \end{tabular} |
|
323 \end{center} |
|
324 |
|
325 You can use \textit{size} in order to test how much the `evil' regular |
|
326 expression $(a^*)^* \cdot b$ grows when taking successive derivatives |
|
327 according the letter $a$ without simplification and then compare it to |
|
328 taking the derivative, but simplify the result. The sizes |
|
329 are given in \texttt{re.scala}. \hfill[1 Mark] |
|
330 |
|
331 \item[(6)] You do not have to implement anything specific under this |
|
332 task. The purpose is that you will be marked for some ``power'' |
|
333 test cases. For example can your matcher decide withing 30 seconds |
|
334 whether the regular expression $(a^*)^*\cdot b$ matches strings of the |
|
335 form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification |
|
336 simplify the regular expression |
|
337 |
|
338 \[ |
|
339 \texttt{SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)} |
|
340 \] |
|
341 |
|
342 \noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested |
|
343 50 or more times.\\ |
|
344 \mbox{}\hfill[1 Mark] |
|
345 \end{itemize} |
|
346 |
|
347 \subsection*{Background} |
|
348 |
|
349 Although easily implementable in Scala, the idea behind the derivative |
|
350 function might not so easy to be seen. To understand its purpose |
|
351 better, assume a regular expression $r$ can match strings of the form |
|
352 $c\!::\!cs$ (that means strings which start with a character $c$ and have |
|
353 some rest, or tail, $cs$). If you take the derivative of $r$ with |
|
354 respect to the character $c$, then you obtain a regular expression |
|
355 that can match all the strings $cs$. In other words, the regular |
|
356 expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$ |
|
357 that can be matched by $r$, except that the $c$ is chopped off. |
|
358 |
|
359 Assume now $r$ can match the string $abc$. If you take the derivative |
|
360 according to $a$ then you obtain a regular expression that can match |
|
361 $bc$ (it is $abc$ where the $a$ has been chopped off). If you now |
|
362 build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you |
|
363 obtain a regular expression that can match the string $c$ (it is $bc$ |
|
364 where $b$ is chopped off). If you finally build the derivative of this |
|
365 according $c$, that is |
|
366 $\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain |
|
367 a regular expression that can match the empty string. You can test |
|
368 whether this is indeed the case using the function nullable, which is |
|
369 what your matcher is doing. |
|
370 |
|
371 The purpose of the $\textit{simp}$ function is to keep the regular |
|
372 expressions small. Normally the derivative function makes the regular |
|
373 expression bigger (see the SEQ case and the example in (2)) and the |
|
374 algorithm would be slower and slower over time. The $\textit{simp}$ |
|
375 function counters this increase in size and the result is that the |
|
376 algorithm is fast throughout. By the way, this algorithm is by Janusz |
|
377 Brzozowski who came up with the idea of derivatives in 1964 in his PhD |
|
378 thesis. |
|
379 |
|
380 \begin{center}\small |
|
381 \url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)} |
|
382 \end{center} |
|
383 |
|
384 |
|
385 If you want to see how badly the regular expression matchers do in |
|
386 Java\footnote{Version 8 and below; Version 9 and above does not seem to be as |
|
387 catastrophic, but still much worse than the regular expression |
|
388 matcher based on derivatives.}, JavaScript and in Python with the |
|
389 `evil' regular expression $(a^*)^*\cdot b$, then have a look at the |
|
390 graphs below (you can try it out for yourself: have a look at the file |
|
391 \texttt{catastrophic9.java}, \texttt{catastrophic.js} and |
|
392 \texttt{catastrophic.py} on KEATS). Compare this with the matcher you |
|
393 have implemented. How long can the string of $a$'s be in your matcher |
|
394 and still stay within the 30 seconds time limit? |
|
395 |
|
396 \begin{center} |
|
397 \begin{tabular}{@{}cc@{}} |
|
398 \multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings |
|
399 $\underbrace{a\ldots a}_{n}$}\bigskip\\ |
|
400 |
|
401 \begin{tikzpicture} |
|
402 \begin{axis}[ |
|
403 xlabel={$n$}, |
|
404 x label style={at={(1.05,0.0)}}, |
|
405 ylabel={time in secs}, |
|
406 y label style={at={(0.06,0.5)}}, |
|
407 enlargelimits=false, |
|
408 xtick={0,5,...,30}, |
|
409 xmax=33, |
|
410 ymax=45, |
|
411 ytick={0,5,...,40}, |
|
412 scaled ticks=false, |
|
413 axis lines=left, |
|
414 width=6cm, |
|
415 height=5.5cm, |
|
416 legend entries={Python, Java 8, JavaScript}, |
|
417 legend pos=north west] |
|
418 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
|
419 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
420 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; |
|
421 \end{axis} |
|
422 \end{tikzpicture} |
|
423 & |
|
424 \begin{tikzpicture} |
|
425 \begin{axis}[ |
|
426 xlabel={$n$}, |
|
427 x label style={at={(1.05,0.0)}}, |
|
428 ylabel={time in secs}, |
|
429 y label style={at={(0.06,0.5)}}, |
|
430 %enlargelimits=false, |
|
431 %xtick={0,5000,...,30000}, |
|
432 xmax=65000, |
|
433 ymax=45, |
|
434 ytick={0,5,...,40}, |
|
435 scaled ticks=false, |
|
436 axis lines=left, |
|
437 width=6cm, |
|
438 height=5.5cm, |
|
439 legend entries={Java 9}, |
|
440 legend pos=north west] |
|
441 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data}; |
|
442 \end{axis} |
|
443 \end{tikzpicture} |
|
444 \end{tabular} |
|
445 \end{center} |
|
446 \newpage |
|
447 |
|
448 \subsection*{Part 2 (4 Marks)} |
|
449 |
|
450 Coming from Java or C++, you might think Scala is a quite esoteric |
|
451 programming language. But remember, some serious companies have built |
|
452 their business on |
|
453 Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} |
|
454 And there are far, far more esoteric languages out there. One is |
|
455 called \emph{brainf***}. You are asked in this part to implement an |
|
456 interpreter for this language. |
|
457 |
|
458 Urban M\"uller developed brainf*** in 1993. A close relative of this |
|
459 language was already introduced in 1964 by Corado B\"ohm, an Italian |
|
460 computer pioneer, who unfortunately died a few months ago. The main |
|
461 feature of brainf*** is its minimalistic set of instructions---just 8 |
|
462 instructions in total and all of which are single characters. Despite |
|
463 the minimalism, this language has been shown to be Turing |
|
464 complete\ldots{}if this doesn't ring any bell with you: it roughly |
|
465 means that every algorithm we know can, in principle, be implemented in |
|
466 brainf***. It just takes a lot of determination and quite a lot of |
|
467 memory resources. Some relatively sophisticated sample programs in |
|
468 brainf*** are given in the file \texttt{bf.scala}.\bigskip |
35 |
469 |
36 \noindent |
470 \noindent |
37 There are many uses for Deterministic Finite Automata (DFAs), for |
471 As mentioned above, brainf*** has 8 single-character commands, namely |
38 example for testing whether a string matches a pattern or not. DFAs |
472 \texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, |
39 consist of some states (circles) and some transitions (edges) between |
473 \texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is |
40 states. For example the DFA |
474 considered a comment. Brainf*** operates on memory cells containing |
41 |
475 integers. For this it uses a single memory pointer that points at each |
42 \begin{center} |
476 stage to one memory cell. This pointer can be moved forward by one |
43 \begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto, |
477 memory cell by using the command \texttt{'>'}, and backward by using |
44 every state/.style={minimum size=4pt, |
478 \texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase, |
45 inner sep=4pt,draw=blue!50,very thick, |
479 respectively decrease, by 1 the content of the memory cell to which |
46 fill=blue!20}] |
480 the memory pointer currently points to. The commands for input/output |
47 \node[state, initial] (q0) at ( 0,1) {$Q_0$}; |
481 are \texttt{','} and \texttt{'.'}. Output works by reading the content |
48 \node[state] (q1) at ( 1,1) {$Q_1$}; |
482 of the memory cell to which the memory pointer points to and printing |
49 \node[state, accepting] (q2) at ( 2,1) {$Q_2$}; |
483 it out as an ASCII character. Input works the other way, taking some |
50 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
484 user input and storing it in the cell to which the memory pointer |
51 (q1) edge[bend left] node[above] {$b$} (q0) |
485 points to. The commands \texttt{'['} and \texttt{']'} are looping |
52 (q2) edge[bend left=50] node[below] {$b$} (q0) |
486 constructs. Everything in between \texttt{'['} and \texttt{']'} is |
53 (q1) edge node[above] {$a$} (q2) |
487 repeated until a counter (memory cell) reaches zero. A typical |
54 (q2) edge [loop right] node {$a$} () |
488 program in brainf*** looks as follows: |
55 (q0) edge [loop below] node {$b$} (); |
489 |
56 \end{tikzpicture} |
490 \begin{center} |
57 \end{center} |
491 \begin{verbatim} |
|
492 ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
|
493 ..+++.>>.<-.<.+++.------.--------.>>+.>++. |
|
494 \end{verbatim} |
|
495 \end{center} |
58 |
496 |
59 \noindent |
497 \noindent |
60 has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the |
498 This one prints out Hello World\ldots{}obviously. |
61 starting state of the DFA and $Q_2$ is the accepting state. The latter |
499 |
62 is indicated by double lines. In general, a DFA can have any number of |
500 \subsubsection*{Tasks (file bf.scala)} |
63 accepting states, but only a single starting state. |
|
64 |
|
65 Transitions are edges between states labelled with a character. The |
|
66 idea is that if we are in state $Q_0$, say, and get an $a$, we can go |
|
67 to state $Q_1$. If we are in state $Q_2$ and get an $a$, we can stay |
|
68 in state $Q_2$; if we get a $b$ in $Q_2$, then can go to state |
|
69 $Q_0$. The main point of DFAs is that if we are in a state and get a |
|
70 character, it is always clear which is the next state---there can only |
|
71 be at most one. The task of Part 1 is to implement such DFAs in Scala |
|
72 using partial functions for the transitions. |
|
73 |
|
74 A string is accepted by a DFA, if we start in the starting state, |
|
75 follow all transitions according to the string; if we end up in an |
|
76 accepting state, then the string is accepted. If not, the string is |
|
77 not accepted. The technical idea is that DFAs can be used to |
|
78 accept strings from \emph{regular} languages. |
|
79 |
|
80 \subsubsection*{Tasks} |
|
81 |
501 |
82 \begin{itemize} |
502 \begin{itemize} |
83 \item[(1)] Write a polymorphic function, called \texttt{share}, that |
503 \item[(2a)] Brainf*** memory is represented by a \texttt{Map} from |
84 decides whether two sets share some elements (i.e.~the intersection |
504 integers to integers. The empty memory is represented by |
85 is not empty).\hfill[1 Mark] |
505 \texttt{Map()}, that is nothing is stored in the |
86 |
506 memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at |
87 \item[(2)] The transitions of DFAs will be implemented as partial |
507 memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The |
88 functions. These functions will have the type (state, |
508 convention is that if we query the memory at a location that is |
89 character)-pair to state, that is their input will be a (state, |
509 \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write |
90 character)-pair and they return a state. For example the transitions |
510 a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and |
91 of the DFA shown above can be defined as the following |
511 a memory pointer (an \texttt{Int}) as argument, and safely reads the |
92 partial function: |
512 corresponding memory location. If the \texttt{Map} is not defined at |
93 |
513 the memory pointer, \texttt{sread} returns \texttt{0}. |
94 \begin{lstlisting}[language=Scala,numbers=none] |
514 |
95 val dfa_trans : PartialFunction[(State,Char), State] = |
515 Write another function \texttt{write}, which takes a memory, a |
96 { case (Q0, 'a') => Q1 |
516 memory pointer and an integer value as argument and updates the |
97 case (Q0, 'b') => Q0 |
517 \texttt{Map} with the value at the given memory location. As usual |
98 case (Q1, 'a') => Q2 |
518 the \texttt{Map} is not updated `in-place' but a new map is created |
99 case (Q1, 'b') => Q0 |
519 with the same data, except the value is stored at the given memory |
100 case (Q2, 'a') => Q2 |
520 pointer.\hfill[1 Mark] |
101 case (Q2, 'b') => Q0 |
521 |
102 } |
522 \item[(2b)] Write two functions, \texttt{jumpRight} and |
103 \end{lstlisting} |
523 \texttt{jumpLeft} that are needed to implement the loop constructs |
104 |
524 of brainf***. They take a program (a \texttt{String}) and a program |
105 The main point of partial functions (as opposed to ``normal'' |
525 counter (an \texttt{Int}) as argument and move right (respectively |
106 functions) is that they do not have to be defined everywhere. For |
526 left) in the string in order to find the \textbf{matching} |
107 example the transitions above only mention characters $a$ and $b$, |
527 opening/closing bracket. For example, given the following program |
108 but leave out any other characters. Partial functions come with a |
528 with the program counter indicated by an arrow: |
109 method \texttt{isDefinedAt} that can be used to check whether an |
529 |
110 input produces a result or not. For example |
530 \begin{center} |
111 |
531 \texttt{--[\barbelow{.}.+>--],>,++} |
112 \begin{lstlisting}[language=Scala,numbers=none] |
532 \end{center} |
113 dfa_trans.isDefinedAt((Q0, 'a')) |
533 |
114 dfa_trans.isDefinedAt((Q0, 'c')) |
534 then the matching closing bracket is in 9th position (counting from 0) and |
115 \end{lstlisting} |
535 \texttt{jumpRight} is supposed to return the position just after this |
116 |
|
117 \noindent |
|
118 gives \texttt{true} in the first case and \texttt{false} in the |
|
119 second. There is also a method \texttt{lift} that transforms a |
|
120 partial function into a ``normal'' function returning an optional |
|
121 value: if the partial function is defined on the input, the lifted |
|
122 function will return \texttt{Some}; if it is not defined, then |
|
123 \texttt{None}. |
|
124 |
536 |
125 Write a function that takes a transition and a (state, character)-pair as arguments |
537 \begin{center} |
126 and produces an optional state (the state specified by the partial transition |
538 \texttt{--[..+>--]\barbelow{,}>,++} |
127 function whenever it is defined; if the transition function is undefined, |
539 \end{center} |
128 return \texttt{None}).\hfill\mbox{[1 Mark]} |
540 |
129 |
541 meaning it jumps to after the loop. Similarly, if you are in 8th position |
130 \item[(3)] |
542 then \texttt{jumpLeft} is supposed to jump to just after the opening |
131 Write a function that ``lifts'' the function in (2) from characters to strings. That |
543 bracket (that is jumping to the beginning of the loop): |
132 is, write a function that takes a transition, a state and a list of characters |
544 |
133 as arguments and produces the state generated by following the transitions for |
545 \begin{center} |
134 each character in the list. For example if you are in state $Q_0$ in the DFA above |
546 \texttt{--[..+>-\barbelow{-}],>,++} |
135 and have the list \texttt{List(a,a,a,b,b,a)}, then you need to return the |
547 \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad |
136 state $Q_1$ (as option since there might not be such a state in general).\\ |
548 \texttt{--[\barbelow{.}.+>--],>,++} |
137 \mbox{}\hfill\mbox{[1 Mark]} |
549 \end{center} |
|
550 |
|
551 Unfortunately we have to take into account that there might be |
|
552 other opening and closing brackets on the `way' to find the |
|
553 matching bracket. For example in the brainf*** program |
|
554 |
|
555 \begin{center} |
|
556 \texttt{--[\barbelow{.}.[+>]--],>,++} |
|
557 \end{center} |
|
558 |
|
559 we do not want to return the index for the \texttt{'-'} in the 9th |
|
560 position, but the program counter for \texttt{','} in 12th |
|
561 position. The easiest to find out whether a bracket is matched is by |
|
562 using levels (which are the third argument in \texttt{jumpLeft} and |
|
563 \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the |
|
564 level by one whenever you find an opening bracket and decrease by |
|
565 one for a closing bracket. Then in \texttt{jumpRight} you are looking |
|
566 for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you |
|
567 do the opposite. In this way you can find \textbf{matching} brackets |
|
568 in strings such as |
|
569 |
|
570 \begin{center} |
|
571 \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++} |
|
572 \end{center} |
|
573 |
|
574 for which \texttt{jumpRight} should produce the position: |
|
575 |
|
576 \begin{center} |
|
577 \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++} |
|
578 \end{center} |
|
579 |
|
580 It is also possible that the position returned by \texttt{jumpRight} or |
|
581 \texttt{jumpLeft} is outside the string in cases where there are |
|
582 no matching brackets. For example |
|
583 |
|
584 \begin{center} |
|
585 \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++} |
|
586 \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad |
|
587 \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}} |
|
588 \end{center} |
|
589 \hfill[1 Mark] |
|
590 |
|
591 |
|
592 \item[(2c)] Write a recursive function \texttt{run} that executes a |
|
593 brainf*** program. It takes a program, a program counter, a memory |
|
594 pointer and a memory as arguments. If the program counter is outside |
|
595 the program string, the execution stops and \texttt{run} returns the |
|
596 memory. If the program counter is inside the string, it reads the |
|
597 corresponding character and updates the program counter \texttt{pc}, |
|
598 memory pointer \texttt{mp} and memory \texttt{mem} according to the |
|
599 rules shown in Figure~\ref{comms}. It then calls recursively |
|
600 \texttt{run} with the updated data. |
|
601 |
|
602 Write another function \texttt{start} that calls \texttt{run} with a |
|
603 given brainfu** program and memory, and the program counter and memory pointer |
|
604 set to~$0$. Like \texttt{run} it returns the memory after the execution |
|
605 of the program finishes. You can test your brainf**k interpreter with the |
|
606 Sierpinski triangle or the Hello world programs or have a look at |
|
607 |
|
608 \begin{center} |
|
609 \url{https://esolangs.org/wiki/Brainfuck} |
|
610 \end{center}\hfill[2 Marks] |
138 |
611 |
139 \item[(4)] DFAs are defined as a triple: (starting state, transitions, |
612 \begin{figure}[p] |
140 set of accepting states). Write a function \texttt{accepts} that tests whether |
613 \begin{center} |
141 a string is accepted by an DFA or not. For this start in the |
614 \begin{tabular}{|@{}p{0.8cm}|l|} |
142 starting state of the DFA, use the function under (3) to calculate |
615 \hline |
143 the state after following all transitions according to the |
616 \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
144 characters in the string. If the resulting state is an accepting state, |
617 $\bullet$ & $\texttt{pc} + 1$\\ |
145 return \texttt{true}; otherwise \texttt{false}.\\\mbox{}\hfill\mbox{[1 Mark]} |
618 $\bullet$ & $\texttt{mp} + 1$\\ |
146 \end{itemize} |
619 $\bullet$ & \texttt{mem} unchanged |
147 |
620 \end{tabular}\\\hline |
148 |
621 \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
149 \subsection*{Part 2 (Non-Deterministic Finite Automata)} |
622 $\bullet$ & $\texttt{pc} + 1$\\ |
150 |
623 $\bullet$ & $\texttt{mp} - 1$\\ |
151 The main point of DFAs is that for every given state and character |
624 $\bullet$ & \texttt{mem} unchanged |
152 there is at most one next state (one if the transition is defined; |
625 \end{tabular}\\\hline |
153 none otherwise). However, this restriction to at most one state can be |
626 \hfill\texttt{'+'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
154 quite limiting for some applications.\footnote{Though there is a |
627 $\bullet$ & $\texttt{pc} + 1$\\ |
155 curious fact that every (less restricted) NFA can be translated into |
628 $\bullet$ & $\texttt{mp}$ unchanged\\ |
156 an ``equivalent'' DFA, whereby accepting means accepting the same |
629 $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) + 1}\\ |
157 set of strings. However this might increase drastically the number |
630 \end{tabular}\\\hline |
158 of states in the DFA.} Non-Deterministic Automata (NFAs) remove |
631 \hfill\texttt{'-'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
159 this restriction: there can be more than one starting state, and given |
632 $\bullet$ & $\texttt{pc} + 1$\\ |
160 a state and a character there can be more than one next |
633 $\bullet$ & $\texttt{mp}$ unchanged\\ |
161 state. Consider for example the NFA |
634 $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) - 1}\\ |
162 |
635 \end{tabular}\\\hline |
163 \begin{center} |
636 \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
164 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
637 $\bullet$ & $\texttt{pc} + 1$\\ |
165 every state/.style={minimum size=0pt, |
638 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ |
166 draw=blue!50,very thick,fill=blue!20},] |
639 $\bullet$ & print out \,\texttt{mem(mp)} as a character\\ |
167 \node[state,initial] (R_1) {$R_1$}; |
640 \end{tabular}\\\hline |
168 \node[state,initial] (R_2) [above=of R_1] {$R_2$}; |
641 \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
169 \node[state, accepting] (R_3) [right=of R_1] {$R_3$}; |
642 $\bullet$ & $\texttt{pc} + 1$\\ |
170 \path[->] (R_1) edge node [below] {$b$} (R_3); |
643 $\bullet$ & $\texttt{mp}$ unchanged\\ |
171 \path[->] (R_2) edge [bend left] node [above] {$a$} (R_3); |
644 $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ |
172 \path[->] (R_1) edge [bend left] node [left] {$c$} (R_2); |
645 \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} |
173 \path[->] (R_2) edge [bend left] node [right] {$a$} (R_1); |
646 \end{tabular}\\\hline |
174 \end{tikzpicture} |
647 \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
175 \end{center} |
648 \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\ |
176 |
649 $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\ |
177 \noindent |
650 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\ |
178 where in state $R_2$ if we get an $a$, we can go to state $R_1$ |
651 \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\ |
179 \emph{or} $R_3$. If we want to find out whether an NFA accepts a |
652 $\bullet$ & $\texttt{pc} + 1$\\ |
180 string, then we need to explore both possibilities. We will do this |
653 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ |
181 ``exploration'' in the tasks below in a breadth-first manner. |
654 \end{tabular} |
182 |
655 \\\hline |
183 |
656 \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
184 The feature of having more than one next state in NFAs will be |
657 \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\ |
185 implemented by having a \emph{set} of partial transition functions |
658 $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\ |
186 (DFAs had only one). For example the NFA shown above will be |
659 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\ |
187 represented by the set of partial functions |
660 \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\ |
188 |
661 $\bullet$ & $\texttt{pc} + 1$\\ |
189 \begin{lstlisting}[language=Scala,numbers=none] |
662 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ |
190 val nfa_trans : NTrans = Set( |
663 \end{tabular}\\\hline |
191 { case (R1, 'c') => R2 }, |
664 any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} |
192 { case (R1, 'b') => R3 }, |
665 $\bullet$ & $\texttt{pc} + 1$\\ |
193 { case (R2, 'a') => R1 }, |
666 $\bullet$ & \texttt{mp} and \texttt{mem} unchanged |
194 { case (R2, 'a') => R3 } |
667 \end{tabular}\\ |
195 ) |
668 \hline |
196 \end{lstlisting} |
669 \end{tabular} |
197 |
670 \end{center} |
198 \noindent |
671 \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc}, |
199 The point is that the 3rd element in this set makes sure that in state $R_2$ and |
672 memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}} |
200 given an $a$, we can go to state $R_1$; and the 4th element, in $R_2$, |
673 \end{figure} |
201 given an $a$, we can also go to state $R_3$. When following |
674 \end{itemize}\bigskip |
202 transitions from a state, we have to look at all partial functions in |
675 |
203 the set and generate the set of \emph{all} possible next states. |
676 |
204 |
677 |
205 \subsubsection*{Tasks} |
|
206 |
|
207 \begin{itemize} |
|
208 \item[(5)] |
|
209 Write a function \texttt{nnext} which takes a transition set, a state |
|
210 and a character as arguments, and calculates all possible next states |
|
211 (returned as set).\\ |
|
212 \mbox{}\hfill\mbox{[1 Mark]} |
|
213 |
|
214 \item[(6)] Write a function \texttt{nnexts} which takes a transition |
|
215 set, a \emph{set} of states and a character as arguments, and |
|
216 calculates \emph{all} possible next states that can be reached from |
|
217 any state in the set.\mbox{}\hfill\mbox{[1 Mark]} |
|
218 |
|
219 \item[(7)] Like in (3), write a function \texttt{nnextss} that lifts |
|
220 \texttt{nnexts} from (6) from single characters to lists of characters. |
|
221 \mbox{}\hfill\mbox{[1 Mark]} |
|
222 |
|
223 \item[(8)] NFAs are also defined as a triple: (set of staring states, |
|
224 set of transitions, set of accepting states). Write a function |
|
225 \texttt{naccepts} that tests whether a string is accepted by an NFA |
|
226 or not. For this start in all starting states of the NFA, use the |
|
227 function under (7) to calculate the set of states following all |
|
228 transitions according to the characters in the string. If the |
|
229 resulting set of states shares at least a single state with the set |
|
230 of accepting states, return \texttt{true}; otherwise \texttt{false}. |
|
231 Use the function under (1) in order to test whether these two sets |
|
232 of states share any states or not.\mbox{}\hfill\mbox{[1 Mark]} |
|
233 |
|
234 \item[(9)] Since we explore in functions (6) and (7) all possible next |
|
235 states, we decide whether a string is accepted in a breadth-first |
|
236 manner. (Depth-first would be to choose one state, follow all next |
|
237 states of this single state; check whether it leads to an accepting |
|
238 state. If not, we backtrack and choose another state). The |
|
239 disadvantage of breadth-first search is that at every step a |
|
240 non-empty set of states are ``active''\ldots{} states that need to |
|
241 be followed at the same time. Write similar functions as in (7) and |
|
242 (8), but instead of returning states or a boolean, calculate the |
|
243 number of states that need to be followed in each step. The function |
|
244 \texttt{max\_accept} should then return the maximum of all these |
|
245 numbers. |
|
246 |
|
247 As a test case, consider again the NFA shown above. At the beginning |
|
248 the number of active states will be 2 (since there are two starting |
|
249 states, namely $R_1$ and $R_2$). If we get an $a$, there will be |
|
250 still 2 active states, namely $R_1$ and $R_3$ both reachable from |
|
251 $R_2$. There is no transition for $a$ and $R_1$. So for a string, |
|
252 say, $ab$ which is accepted by the NFA, the maximum number of active |
|
253 states is 2 (it is not possible that all three states of this NFA |
|
254 are active at the same time; is it possible that no state is |
|
255 active?). \hfill\mbox{[2 Marks]} |
|
256 |
|
257 |
|
258 \end{itemize} |
|
259 |
|
260 |
678 |
261 \end{document} |
679 \end{document} |
262 |
680 |
263 |
681 |
264 %%% Local Variables: |
682 %%% Local Variables: |