12 at 5pm. Make sure the files you submit can be processed by just |
12 at 5pm. Make sure the files you submit can be processed by just |
13 calling \texttt{scala <<filename.scala>>}.\bigskip |
13 calling \texttt{scala <<filename.scala>>}.\bigskip |
14 |
14 |
15 \noindent |
15 \noindent |
16 \textbf{Important:} Do not use any mutable data structures in your |
16 \textbf{Important:} Do not use any mutable data structures in your |
17 submission! They are not needed. This means you cannot use |
17 submission! They are not needed. This means you cannot use |
18 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
18 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your |
19 code! It has a different meaning in Scala, than in Java. Do not use |
19 code! It has a different meaning in Scala, than in Java. Do not use |
20 \texttt{var}! This declares a mutable variable. Make sure the |
20 \texttt{var}! This declares a mutable variable. Make sure the |
21 functions you submit are defined on the ``top-level'' of Scala, not |
21 functions you submit are defined on the ``top-level'' of Scala, not |
22 inside a class or object. Also note that the running time will be |
22 inside a class or object. Also note that when marking, the running time |
23 restricted to a maximum of 360 seconds on my laptop. |
23 will be restricted to a maximum of 360 seconds on my laptop. |
24 |
24 |
25 |
25 |
26 \subsection*{Disclaimer} |
26 \subsection*{Disclaimer} |
27 |
27 |
28 It should be understood that the work you submit represents your own |
28 It should be understood that the work you submit represents your own |
33 |
33 |
34 \subsection*{Part 1 (Deterministic Finite Automata)} |
34 \subsection*{Part 1 (Deterministic Finite Automata)} |
35 |
35 |
36 \noindent |
36 \noindent |
37 There are many uses for Deterministic Finite Automata (DFAs), for |
37 There are many uses for Deterministic Finite Automata (DFAs), for |
38 example testing whether a string should be accepted or not. The main |
38 example for testing whether a string matches a pattern or not. DFAs |
39 idea is that DFAs consist of some states (circles) and transitions |
39 consist of some states (circles) and transitions (edges) between |
40 (edges) between states. For example consider the DFA |
40 states. For example consider the DFA |
41 |
41 |
42 \begin{center} |
42 \begin{center} |
43 \begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto, |
43 \begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto, |
44 every state/.style={minimum size=4pt, |
44 every state/.style={minimum size=4pt, |
45 inner sep=4pt,draw=blue!50,very thick, |
45 inner sep=4pt,draw=blue!50,very thick, |
55 (q0) edge [loop below] node {$b$} (); |
55 (q0) edge [loop below] node {$b$} (); |
56 \end{tikzpicture} |
56 \end{tikzpicture} |
57 \end{center} |
57 \end{center} |
58 |
58 |
59 \noindent |
59 \noindent |
60 where there are three states ($Q_0$, $Q_1$ and $Q_2$). The DFA has a |
60 has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the |
61 starting state ($Q_0$) and an accepting state ($Q_2$), the latter |
61 starting state of the DFA and $Q_2$ is the accepting state. The latter |
62 indicated by double lines. In general, a DFA can have any number of |
62 indicated by double lines. In general, a DFA can have any number of |
63 accepting states, but only a single starting state (in this example |
63 accepting states, but only a single starting state. |
64 only $a$ and $b$). |
|
65 |
64 |
66 Transitions are edges between states labelled with a character. The |
65 Transitions are edges between states labelled with a character. The |
67 idea is that if I am in state $Q_0$, say, and get an $a$, I can go to |
66 idea is that if we are in state $Q_0$, say, and get an $a$, we can go |
68 state $Q_1$. If I am in state $Q_2$ and get an $a$, I can stay in |
67 to state $Q_1$. If we are in state $Q_2$ and get an $a$, we can stay |
69 state $Q_2$; if I get a $b$ in $Q_2$, then I have to go to state |
68 in state $Q_2$; if we get a $b$ in $Q_2$, then we have to go to state |
70 $Q_0$. The main point of DFAs is that if I am in a state and get a |
69 $Q_0$. The main point of DFAs is that if we are in a state and get a |
71 character, it is always clear which is the next state---there can only |
70 character, it is always clear which is the next state---there can only |
72 be at most one. The task of Part 1 is to implement such DFAs in Scala |
71 be at most one. The task of Part 1 is to implement such DFAs in Scala |
73 using partial functions for the transitions. |
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. |
74 |
79 |
75 \subsubsection*{Tasks} |
80 \subsubsection*{Tasks} |
76 |
81 |
77 \begin{itemize} |
82 \begin{itemize} |
78 \item[(1)] Write a polymorphic function, called \texttt{share}, that |
83 \item[(1)] Write a polymorphic function, called \texttt{share}, that |
79 decides whether two sets share some elements (i.e.~the intersection |
84 decides whether two sets share some elements (i.e.~the intersection |
80 is not empty).\hfill[1 Mark] |
85 is not empty).\hfill[1 Mark] |
81 |
86 |
82 \item[(2)] The transitions of DFAs are given by partial functions, |
87 \item[(2)] The transitions of DFAs will be implemented as partial |
83 with the type of (state, character)-pair to state. For example |
88 functions. These functions will have the type (state, |
84 the transitions of the DFA given above can be defined as |
89 character)-pair to state, that is their input will be a (state, |
|
90 character)-pair and they return a state. For example the transitions |
|
91 of the DFA shown above can be defined as the following |
|
92 partial function: |
85 |
93 |
86 \begin{lstlisting}[language=Scala,numbers=none] |
94 \begin{lstlisting}[language=Scala,numbers=none] |
87 val dfa_trans : PartialFunction[(State,Char), State] = |
95 val dfa_trans : PartialFunction[(State,Char), State] = |
88 { case (Q0, 'a') => Q1 |
96 { case (Q0, 'a') => Q1 |
89 case (Q0, 'b') => Q0 |
97 case (Q0, 'b') => Q0 |
92 case (Q2, 'a') => Q2 |
100 case (Q2, 'a') => Q2 |
93 case (Q2, 'b') => Q0 |
101 case (Q2, 'b') => Q0 |
94 } |
102 } |
95 \end{lstlisting} |
103 \end{lstlisting} |
96 |
104 |
97 The main idea of partial functions (as opposed to functions) is that they |
105 The main point of partial functions (as opposed to ``normal'' |
98 do not have to be defined everywhere. For example the transitions |
106 functions) is that they do not have to be defined everywhere. For |
99 above only mention characters $a$ and $b$, but leave out any other |
107 example the transitions above only mention characters $a$ and $b$, |
100 characters. Partial functions come with a method \texttt{isDefinedAt} |
108 but leave out any other characters. Partial functions come with a |
101 that can be used to check whether an input produces a result |
109 method \texttt{isDefinedAt} that can be used to check whether an |
102 or not. For example |
110 input produces a result or not. For example |
103 |
111 |
104 \begin{lstlisting}[language=Scala,numbers=none] |
112 \begin{lstlisting}[language=Scala,numbers=none] |
105 dfa_trans.isDefinedAt((Q0, 'a')) |
113 dfa_trans.isDefinedAt((Q0, 'a')) |
106 dfa_trans.isDefinedAt((Q0, 'c')) |
114 dfa_trans.isDefinedAt((Q0, 'c')) |
107 \end{lstlisting} |
115 \end{lstlisting} |
108 |
116 |
109 \noindent |
117 \noindent |
110 gives \texttt{true} in the first case and \texttt{false} in the second. |
118 gives \texttt{true} in the first case and \texttt{false} in the |
111 |
119 second. There is also a method \texttt{lift} that transformes a |
112 Write a function that takes transition and a (state, character)-pair as arguments |
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 |
|
125 Write a function that takes a transition and a (state, character)-pair as arguments |
113 and produces an optional state (the state specified by the partial transition |
126 and produces an optional state (the state specified by the partial transition |
114 function whenever it is defined; if the transition function is undefined, |
127 function whenever it is defined; if the transition function is undefined, |
115 return None).\hfill\mbox{[1 Mark]} |
128 return \texttt{None}).\hfill\mbox{[1 Mark]} |
116 |
129 |
117 \item[(3)] |
130 \item[(3)] |
118 Write a function that ``lifts'' the function in (2) from characters to strings. That |
131 Write a function that ``lifts'' the function in (2) from characters to strings. That |
119 is, write a function that takes a transition, a state and a list of characters |
132 is, write a function that takes a transition, a state and a list of characters |
120 as arguments and produces the state generated by following the transitions for |
133 as arguments and produces the state generated by following the transitions for |
121 each character in the list. For example you are in state $Q_0$ in the DFA above |
134 each character in the list. For example if you are in state $Q_0$ in the DFA above |
122 and have the list \texttt{List(a,a,a,b,b,a)}, then you need to generate the |
135 and have the list \texttt{List(a,a,a,b,b,a)}, then you need to return the |
123 state $Q_1$ (as option since there might not be such a state).\\ |
136 state $Q_1$ (as option since there might not be such a state in general).\\ |
124 \mbox{}\hfill\mbox{[1 Mark]} |
137 \mbox{}\hfill\mbox{[1 Mark]} |
125 |
138 |
126 \item[(4)] DFAs are defined as a triple: (staring state, transitions, final states). |
139 \item[(4)] DFAs are defined as a triple: (staring state, transitions, |
127 Write a function \texttt{accepts} that tests whether a string is accepted |
140 set of accepting states). Write a function \texttt{accepts} that tests whether |
128 by an DFA or not. For this start in the starting state of the DFA, |
141 a string is accepted by an DFA or not. For this start in the |
129 use the function under (3) to calculate the state after following all transitions |
142 starting state of the DFA, use the function under (3) to calculate |
130 according to the characters in the string. If the state is a final state, return |
143 the state after following all transitions according to the |
131 true; otherwise false.\\\mbox{}\hfill\mbox{[1 Mark]} |
144 characters in the string. If the resulting state is an accepting state, |
|
145 return \texttt{true}; otherwise \texttt{false}.\\\mbox{}\hfill\mbox{[1 Mark]} |
132 \end{itemize} |
146 \end{itemize} |
133 |
147 |
134 |
148 |
135 \subsection*{Part 2 (Non-Deterministic Finite Automata)} |
149 \subsection*{Part 2 (Non-Deterministic Finite Automata)} |
136 |
150 |
137 The main point of DFAs is that for every given state and character |
151 The main point of DFAs is that for every given state and character |
138 there is at most one next state (one if the transition is defined; |
152 there is at most one next state (one if the transition is defined; |
139 none otherwise). However, this restriction to at most one state can be |
153 none otherwise). However, this restriction to at most one state can be |
140 quite limiting for some applications.\footnote{Though there is a |
154 quite limiting for some applications.\footnote{Though there is a |
141 curious fact that every NFA can be translated into an ``equivalent'' |
155 curious fact that every (less restricted) NFA can be translated into |
142 DFA, that is accepting the same set of strings. However this might |
156 an ``equivalent'' DFA, whereby accepting means accepting the same |
143 increase drastically the number of states in the DFA.} |
157 set of strings. However this might increase drastically the number |
144 Non-Deterministic Automata (NFAs) remove this restriction: there can |
158 of states in the DFA.} Non-Deterministic Automata (NFAs) remove |
145 be more than one starting state, and given a state and a character |
159 this restriction: there can be more than one starting state, and given |
146 there can be more than one next state. Consider for example |
160 a state and a character there can be more than one next |
|
161 state. Consider for example the NFA |
147 |
162 |
148 \begin{center} |
163 \begin{center} |
149 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
164 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
150 every state/.style={minimum size=0pt, |
165 every state/.style={minimum size=0pt, |
151 draw=blue!50,very thick,fill=blue!20},] |
166 draw=blue!50,very thick,fill=blue!20},] |
158 \path[->] (R_2) edge [bend left] node [right] {$a$} (R_1); |
173 \path[->] (R_2) edge [bend left] node [right] {$a$} (R_1); |
159 \end{tikzpicture} |
174 \end{tikzpicture} |
160 \end{center} |
175 \end{center} |
161 |
176 |
162 \noindent |
177 \noindent |
163 where in state $R_2$ if you get an $a$, you can go to state $R_1$ |
178 where in state $R_2$ if we get an $a$, we can go to state $R_1$ |
164 \emph{or} $R_3$. If we want to find out whether a NFA accepts a |
179 \emph{or} $R_3$. If we want to find out whether an NFA accepts a |
165 string, then we need to explore both possibilities. We will do this |
180 string, then we need to explore both possibilities. We will do this |
166 ``exploration'' in the tasks below in a breath-first manner. |
181 ``exploration'' in the tasks below in a breadth-first manner. |
167 The possibility of having more than one next state in NFAs will |
182 |
168 be implemented by having a \emph{set} of partial transition |
183 |
169 functions. For example the NFA shown above will be represented by the |
184 The feature of having more than one next state in NFAs will be |
170 set of partial functions |
185 implemented by having a \emph{set} of partial transition functions |
|
186 (DFAs had only one). For example the NFA shown above will be |
|
187 represented by the set of partial functions |
171 |
188 |
172 \begin{lstlisting}[language=Scala,numbers=none] |
189 \begin{lstlisting}[language=Scala,numbers=none] |
173 val nfa_trans : NTrans = Set( |
190 val nfa_trans : NTrans = Set( |
174 { case (R1, 'c') => R2 }, |
191 { case (R1, 'c') => R2 }, |
175 { case (R1, 'b') => R3 }, |
192 { case (R1, 'b') => R3 }, |
196 \mbox{}\hfill\mbox{[1 Mark]} |
212 \mbox{}\hfill\mbox{[1 Mark]} |
197 |
213 |
198 \item[(6)] Write a function \texttt{nnexts} which takes a transition |
214 \item[(6)] Write a function \texttt{nnexts} which takes a transition |
199 set, a \emph{set} of states and a character as arguments, and |
215 set, a \emph{set} of states and a character as arguments, and |
200 calculates \emph{all} possible next states that can be reached from |
216 calculates \emph{all} possible next states that can be reached from |
201 any state in the set.\\ \mbox{}\hfill\mbox{[1 Mark]} |
217 any state in the set.\mbox{}\hfill\mbox{[1 Mark]} |
202 |
218 |
203 \item[(7)] Like in (3), write a function \texttt{nnextss} that lifts |
219 \item[(7)] Like in (3), write a function \texttt{nnextss} that lifts |
204 \texttt{nnexts} from (6) from single characters to lists of characters. |
220 \texttt{nnexts} from (6) from single characters to lists of characters. |
205 \mbox{}\hfill\mbox{[1 Mark]} |
221 \mbox{}\hfill\mbox{[1 Mark]} |
206 |
222 |
207 \item[(8)] NFAs are also defined as a triple: (set of staring states, |
223 \item[(8)] NFAs are also defined as a triple: (set of staring states, |
208 set of transitions, final states). Write a function |
224 set of transitions, set of accepting states). Write a function |
209 \texttt{naccepts} that tests whether a string is accepted by a NFA |
225 \texttt{naccepts} that tests whether a string is accepted by an NFA |
210 or not. For this start in all starting states of the NFA, use the |
226 or not. For this start in all starting states of the NFA, use the |
211 function under (7) to calculate the set of states following all |
227 function under (7) to calculate the set of states following all |
212 transitions according to the characters in the string. If the set of |
228 transitions according to the characters in the string. If the |
213 states shares and state with the set of final states, return true; |
229 resulting set of states shares at least a single state with the set |
214 otherwise false. Use the function under (1) in order to test |
230 of accepting states, return \texttt{true}; otherwise \texttt{false}. |
215 whether these two sets of states share any |
231 Use the function under (1) in order to test whether these two sets |
216 states\mbox{}\hfill\mbox{[1 Mark]} |
232 of states share any states or not.\mbox{}\hfill\mbox{[1 Mark]} |
217 |
233 |
218 \item[(9)] Since we explore in functions under (6) and (7) all |
234 \item[(9)] Since we explore in functions (6) and (7) all possible next |
219 possible next states, we decide whether a string is accepted in a |
235 states, we decide whether a string is accepted in a breadth-first |
220 breath-first manner. (Depth-first would be to choose one state, |
236 manner. (Depth-first would be to choose one state, follow all next |
221 follow all next states of this single state; check whether it leads |
237 states of this single state; check whether it leads to an accepting |
222 to a accepting state. If not, we backtrack and choose another |
238 state. If not, we backtrack and choose another state). The |
223 state). The disadvantage of breath-first search is that at every |
239 disadvantage of breadth-first search is that at every step a |
224 step a non-empty set of states are ``active''\ldots that need to be |
240 non-empty set of states are ``active''\ldots{} states that need to |
225 followed at the same time. Write similar functions as in (7) and |
241 be followed at the same time. Write similar functions as in (7) and |
226 (8), but instead of returning states or a boolean, these functions |
242 (8), but instead of returning states or a boolean, calculate the |
227 return the number of states that need to be followed in each |
243 number of states that need to be followed in each step. The function |
228 step. The function \texttt{max\_accept} should return the maximum |
244 \texttt{max\_accept} should then return the maximum of all these |
229 of all these numbers. |
245 numbers. |
230 |
246 |
231 Consider again the NFA shown above. At the beginning the number of |
247 As a test case, consider again the NFA shown above. At the beginning |
232 active states will be 2 (since there are two starting states, namely |
248 the number of active states will be 2 (since there are two starting |
233 $R_1$ and $R_2$). If we get an $a$, there will be still 2 active |
249 states, namely $R_1$ and $R_2$). If we get an $a$, there will be |
234 states, namely $R_1$ and $R_3$ both reachable from $R_2$. There is |
250 still 2 active states, namely $R_1$ and $R_3$ both reachable from |
235 no transition for $a$ and $R_1$. So for a string, say, $ab$ which is |
251 $R_2$. There is no transition for $a$ and $R_1$. So for a string, |
236 accepted by the NFA, the maximum number of active states is 2 (it is |
252 say, $ab$ which is accepted by the NFA, the maximum number of active |
237 not possible that all states are active with this NFA; is it possible |
253 states is 2 (it is not possible that all three states of this NFA |
238 that no state is active?). |
254 are active at the same time; is it possible that no state is |
239 \hfill\mbox{[2 Marks]} |
255 active?). \hfill\mbox{[2 Marks]} |
240 |
256 |
241 |
257 |
242 \end{itemize} |
258 \end{itemize} |
243 |
259 |
244 |
260 |