--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw05.tex Fri Mar 03 14:50:47 2017 +0000
@@ -0,0 +1,251 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+\usepackage{../graphics}
+
+\begin{document}
+
+\section*{Replacement Coursework 2 (Automata)}
+
+This coursework is worth 10\%. It is about deterministic and
+non-deterministic finite automata. The coursework is due on ??? March
+at 5pm. Make sure the files you submit can be processed by just
+calling \texttt{scala <<filename.scala>>}.\bigskip
+
+\noindent
+\textbf{Important:} Do not use any mutable data structures in your
+submission! They are not needed. This means you cannot use
+\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
+code! It has a different meaning in Scala, than in Java. Do not use
+\texttt{var}! This declares a mutable variable. Make sure the
+functions you submit are defined on the ``top-level'' of Scala, not
+inside a class or object. Also note that the running time will be
+restricted to a maximum of 360 seconds on my laptop.
+
+
+\subsection*{Disclaimer}
+
+It should be understood that the work you submit represents your own
+effort! You have not copied from anyone else. An exception is the
+Scala code I showed during the lectures or uploaded to KEATS, which
+you can freely use.\bigskip
+
+
+\subsection*{Part 1 (Deterministic Finite Automata)}
+
+\noindent
+There are many uses for Deterministic Finite Automata (DFAs), for
+example testing whether a string should be accepted or not. The main
+idea is that DFAs consist of some states (circles) and transitions
+(edges) between states. For example consider the DFA
+
+\begin{center}
+\begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto,
+ every state/.style={minimum size=4pt,
+ inner sep=4pt,draw=blue!50,very thick,
+ fill=blue!20}]
+ \node[state, initial] (q0) at ( 0,1) {$Q_0$};
+ \node[state] (q1) at ( 1,1) {$Q_1$};
+ \node[state, accepting] (q2) at ( 2,1) {$Q_2$};
+ \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
+ (q1) edge[bend left] node[above] {$b$} (q0)
+ (q2) edge[bend left=50] node[below] {$b$} (q0)
+ (q1) edge node[above] {$a$} (q2)
+ (q2) edge [loop right] node {$a$} ()
+ (q0) edge [loop below] node {$b$} ();
+\end{tikzpicture}
+\end{center}
+
+\noindent
+where there are three states ($Q_0$, $Q_1$ and $Q_2$). The DFA has a
+starting state ($Q_0$) and an accepting state ($Q_2$), the latter
+indicated by double lines. In general, a DFA can have any number of
+accepting states, but only a single starting state (in this example
+only $a$ and $b$).
+
+Transitions are edges between states labelled with a character. The
+idea is that if I am in state $Q_0$, say, and get an $a$, I can go to
+state $Q_1$. If I am in state $Q_2$ and get an $a$, I can stay in
+state $Q_2$; if I get a $b$ in $Q_2$, then I have to go to state
+$Q_0$. The main point of DFAs is that if I am in a state and get a
+character, it is always clear which is the next state---there can only
+be at most one. The task of Part 1 is to implement such DFAs in Scala
+using partial functions for the transitions.
+
+\subsubsection*{Tasks}
+
+\begin{itemize}
+\item[(1)] Write a polymorphic function, called \texttt{share}, that
+ decides whether two sets share some elements (i.e.~the intersection
+ is not empty).\hfill[1 Mark]
+
+\item[(2)] The transitions of DFAs are given by partial functions,
+ with the type of (state, character)-pair to state. For example
+ the transitions of the DFA given above can be defined as
+
+\begin{lstlisting}[language=Scala,numbers=none]
+val dfa_trans : PartialFunction[(State,Char), State] =
+ { case (Q0, 'a') => Q1
+ case (Q0, 'b') => Q0
+ case (Q1, 'a') => Q2
+ case (Q1, 'b') => Q0
+ case (Q2, 'a') => Q2
+ case (Q2, 'b') => Q0
+ }
+\end{lstlisting}
+
+ The main idea of partial functions (as opposed to functions) is that they
+ do not have to be defined everywhere. For example the transitions
+ above only mention characters $a$ and $b$, but leave out any other
+ characters. Partial functions come with a method \texttt{isDefinedAt}
+ that can be used to check whether an input produces a result
+ or not. For example
+
+ \begin{lstlisting}[language=Scala,numbers=none]
+ dfa_trans.isDefinedAt((Q0, 'a'))
+ dfa_trans.isDefinedAt((Q0, 'c'))
+ \end{lstlisting}
+
+ \noindent
+ gives \texttt{true} in the first case and \texttt{false} in the second.
+
+ Write a function that takes transition and a (state, character)-pair as arguments
+ and produces an optional state (the state specified by the partial transition
+ function whenever it is defined; if the transition function is undefined,
+ return None).\hfill\mbox{[1 Mark]}
+
+\item[(3)]
+ Write a function that ``lifts'' the function in (2) from characters to strings. That
+ is, write a function that takes a transition, a state and a list of characters
+ as arguments and produces the state generated by following the transitions for
+ each character in the list. For example you are in state $Q_0$ in the DFA above
+ and have the list \texttt{List(a,a,a,b,b,a)}, then you need to generate the
+ state $Q_1$ (as option since there might not be such a state).\\
+ \mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(4)] DFAs are defined as a triple: (staring state, transitions, final states).
+ Write a function \texttt{accepts} that tests whether a string is accepted
+ by an DFA or not. For this start in the starting state of the DFA,
+ use the function under (3) to calculate the state after following all transitions
+ according to the characters in the string. If the state is a final state, return
+ true; otherwise false.\\\mbox{}\hfill\mbox{[1 Mark]}
+\end{itemize}
+
+
+\subsection*{Part 2 (Non-Deterministic Finite Automata)}
+
+The main point of DFAs is that for every given state and character
+there is at most one next state (one if the transition is defined;
+none otherwise). However, this restriction to at most one state can be
+quite limiting for some applications.\footnote{Though there is a
+ curious fact that every NFA can be translated into an ``equivalent''
+ DFA, that is accepting the same set of strings. However this might
+ increase drastically the number of states in the DFA.}
+Non-Deterministic Automata (NFAs) remove this restriction: there can
+be more than one starting state, and given a state and a character
+there can be more than one next state. Consider for example
+
+\begin{center}
+\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+ every state/.style={minimum size=0pt,
+ draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial] (R_1) {$R_1$};
+\node[state,initial] (R_2) [above=of R_1] {$R_2$};
+\node[state, accepting] (R_3) [right=of R_1] {$R_3$};
+\path[->] (R_1) edge node [below] {$b$} (R_3);
+\path[->] (R_2) edge [bend left] node [above] {$a$} (R_3);
+\path[->] (R_1) edge [bend left] node [left] {$c$} (R_2);
+\path[->] (R_2) edge [bend left] node [right] {$a$} (R_1);
+\end{tikzpicture}
+\end{center}
+
+\noindent
+where in state $R_2$ if you get an $a$, you can go to state $R_1$
+\emph{or} $R_3$. If we want to find out whether a NFA accepts a
+string, then we need to explore both possibilities. We will do this
+``exploration'' in the tasks below in a breath-first manner.
+The possibility of having more than one next state in NFAs will
+be implemented by having a \emph{set} of partial transition
+functions. For example the NFA shown above will be represented by the
+set of partial functions
+
+\begin{lstlisting}[language=Scala,numbers=none]
+val nfa_trans : NTrans = Set(
+ { case (R1, 'c') => R2 },
+ { case (R1, 'b') => R3 },
+ { case (R2, 'a') => R1 },
+ { case (R2, 'a') => R3 }
+)
+\end{lstlisting}
+
+\noindent
+The point is that the 3rd element in this set states that
+in $R_2$ and given an $a$, I can go to state $R_1$; and the
+4th element, in $R_2$, given an $a$, I can go to state $R_3$.
+When following transitions from a state, we have to look at all
+partial functions in the set and generate the set of all possible
+next states.
+
+\subsubsection*{Tasks}
+
+\begin{itemize}
+\item[(5)]
+ Write a function \texttt{nnext} which takes a transition set, a state
+ and a character as arguments, and calculates all possible next states
+ (returned as set).\\
+ \mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(6)] Write a function \texttt{nnexts} which takes a transition
+ set, a \emph{set} of states and a character as arguments, and
+ calculates \emph{all} possible next states that can be reached from
+ any state in the set.\\ \mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(7)] Like in (3), write a function \texttt{nnextss} that lifts
+ \texttt{nnexts} from (6) from single characters to lists of characters.
+ \mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(8)] NFAs are also defined as a triple: (set of staring states,
+ set of transitions, final states). Write a function
+ \texttt{naccepts} that tests whether a string is accepted by a NFA
+ or not. For this start in all starting states of the NFA, use the
+ function under (7) to calculate the set of states following all
+ transitions according to the characters in the string. If the set of
+ states shares and state with the set of final states, return true;
+ otherwise false. Use the function under (1) in order to test
+ whether these two sets of states share any
+ states\mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(9)] Since we explore in functions under (6) and (7) all
+ possible next states, we decide whether a string is accepted in a
+ breath-first manner. (Depth-first would be to choose one state,
+ follow all next states of this single state; check whether it leads
+ to a accepting state. If not, we backtrack and choose another
+ state). The disadvantage of breath-first search is that at every
+ step a non-empty set of states are ``active''\ldots that need to be
+ followed at the same time. Write similar functions as in (7) and
+ (8), but instead of returning states or a boolean, these functions
+ return the number of states that need to be followed in each
+ step. The function \texttt{max\_accept} should return the maximum
+ of all these numbers.
+
+ Consider again the NFA shown above. At the beginning the number of
+ active states will be 2 (since there are two starting states, namely
+ $R_1$ and $R_2$). If we get an $a$, there will be still 2 active
+ states, namely $R_1$ and $R_3$ both reachable from $R_2$. There is
+ no transition for $a$ and $R_1$. So for a string, say, $ab$ which is
+ accepted by the NFA, the maximum number of active states is 2 (it is
+ not possible that all states are active with this NFA; is it possible
+ that no state is active?).
+ \hfill\mbox{[2 Marks]}
+
+
+\end{itemize}
+
+
+\end{document}
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End: