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