6 \begin{document} |
6 \begin{document} |
7 |
7 |
8 \section*{Replacement Coursework 2 (Automata)} |
8 \section*{Replacement Coursework 2 (Automata)} |
9 |
9 |
10 This coursework is worth 10\%. It is about deterministic and |
10 This coursework is worth 10\%. It is about deterministic and |
11 non-deterministic finite automata. The coursework is due on ??? March |
11 non-deterministic finite automata. The coursework is due on 21 March |
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 |
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 for testing whether a string matches a pattern or not. DFAs |
38 example for testing whether a string matches a pattern or not. DFAs |
39 consist of some states (circles) and transitions (edges) between |
39 consist of some states (circles) and some transitions (edges) between |
40 states. For example consider the DFA |
40 states. For example 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, |
57 \end{center} |
57 \end{center} |
58 |
58 |
59 \noindent |
59 \noindent |
60 has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the |
60 has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the |
61 starting state of the DFA and $Q_2$ is the accepting state. 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 is indicated by double lines. In general, a DFA can have any number of |
63 accepting states, but only a single starting state. |
63 accepting states, but only a single starting state. |
64 |
64 |
65 Transitions are edges between states labelled with a character. The |
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 |
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 |
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 we have to go to state |
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 |
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 |
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 |
71 be at most one. The task of Part 1 is to implement such DFAs in Scala |
72 using partial functions for the transitions. |
72 using partial functions for the transitions. |
73 |
73 |
107 example the transitions above only mention characters $a$ and $b$, |
107 example the transitions above only mention characters $a$ and $b$, |
108 but leave out any other characters. Partial functions come with a |
108 but leave out any other characters. Partial functions come with a |
109 method \texttt{isDefinedAt} that can be used to check whether an |
109 method \texttt{isDefinedAt} that can be used to check whether an |
110 input produces a result or not. For example |
110 input produces a result or not. For example |
111 |
111 |
112 \begin{lstlisting}[language=Scala,numbers=none] |
112 \begin{lstlisting}[language=Scala,numbers=none] |
113 dfa_trans.isDefinedAt((Q0, 'a')) |
113 dfa_trans.isDefinedAt((Q0, 'a')) |
114 dfa_trans.isDefinedAt((Q0, 'c')) |
114 dfa_trans.isDefinedAt((Q0, 'c')) |
115 \end{lstlisting} |
115 \end{lstlisting} |
116 |
116 |
117 \noindent |
117 \noindent |
118 gives \texttt{true} in the first case and \texttt{false} in the |
118 gives \texttt{true} in the first case and \texttt{false} in the |
119 second. There is also a method \texttt{lift} that transformes a |
119 second. There is also a method \texttt{lift} that transforms a |
120 partial function into a ``normal'' function returning an optional |
120 partial function into a ``normal'' function returning an optional |
121 value: if the partial function is defined on the input, the lifted |
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 |
122 function will return \texttt{Some}; if it is not defined, then |
123 \texttt{None}. |
123 \texttt{None}. |
124 |
124 |
134 each character in the list. For example if 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 |
135 and have the list \texttt{List(a,a,a,b,b,a)}, then you need to return the |
135 and have the list \texttt{List(a,a,a,b,b,a)}, then you need to return the |
136 state $Q_1$ (as option since there might not be such a state in general).\\ |
136 state $Q_1$ (as option since there might not be such a state in general).\\ |
137 \mbox{}\hfill\mbox{[1 Mark]} |
137 \mbox{}\hfill\mbox{[1 Mark]} |
138 |
138 |
139 \item[(4)] DFAs are defined as a triple: (staring state, transitions, |
139 \item[(4)] DFAs are defined as a triple: (starting state, transitions, |
140 set of accepting states). Write a function \texttt{accepts} that tests whether |
140 set of accepting states). Write a function \texttt{accepts} that tests whether |
141 a string is accepted by an DFA or not. For this start in the |
141 a string is accepted by an DFA or not. For this start in the |
142 starting state of the DFA, use the function under (3) to calculate |
142 starting state of the DFA, use the function under (3) to calculate |
143 the state after following all transitions according to the |
143 the state after following all transitions according to the |
144 characters in the string. If the resulting state is an accepting state, |
144 characters in the string. If the resulting state is an accepting state, |
194 { case (R2, 'a') => R3 } |
194 { case (R2, 'a') => R3 } |
195 ) |
195 ) |
196 \end{lstlisting} |
196 \end{lstlisting} |
197 |
197 |
198 \noindent |
198 \noindent |
199 The point is that the 3rd element in this set states that in $R_2$ and |
199 The point is that the 3rd element in this set makes sure that in state $R_2$ and |
200 given an $a$, we can go to state $R_1$; and the 4th element, in $R_2$, |
200 given an $a$, we can go to state $R_1$; and the 4th element, in $R_2$, |
201 given an $a$, we can also go to state $R_3$. When following |
201 given an $a$, we can also go to state $R_3$. When following |
202 transitions from a state, we have to look at all partial functions in |
202 transitions from a state, we have to look at all partial functions in |
203 the set and generate the set of \emph{all} possible next states. |
203 the set and generate the set of \emph{all} possible next states. |
204 |
204 |