--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw08.tex Thu Nov 29 17:15:11 2018 +0000
@@ -0,0 +1,267 @@
+\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 21 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 when marking, 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 for testing whether a string matches a pattern or not. DFAs
+consist of some states (circles) and some transitions (edges) between
+states. For example 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
+has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the
+starting state of the DFA and $Q_2$ is the accepting state. The latter
+is indicated by double lines. In general, a DFA can have any number of
+accepting states, but only a single starting state.
+
+Transitions are edges between states labelled with a character. The
+idea is that if we are in state $Q_0$, say, and get an $a$, we can go
+to state $Q_1$. If we are in state $Q_2$ and get an $a$, we can stay
+in state $Q_2$; if we get a $b$ in $Q_2$, then can go to state
+$Q_0$. The main point of DFAs is that if we are 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.
+
+A string is accepted by a DFA, if we start in the starting state,
+follow all transitions according to the string; if we end up in an
+accepting state, then the string is accepted. If not, the string is
+not accepted. The technical idea is that DFAs can be used to
+accept strings from \emph{regular} languages.
+
+\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 will be implemented as partial
+ functions. These functions will have the type (state,
+ character)-pair to state, that is their input will be a (state,
+ character)-pair and they return a state. For example the transitions
+ of the DFA shown above can be defined as the following
+ partial function:
+
+\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 point of partial functions (as opposed to ``normal''
+ 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. There is also a method \texttt{lift} that transforms a
+ partial function into a ``normal'' function returning an optional
+ value: if the partial function is defined on the input, the lifted
+ function will return \texttt{Some}; if it is not defined, then
+ \texttt{None}.
+
+ Write a function that takes a 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 \texttt{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 if 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 return the
+ state $Q_1$ (as option since there might not be such a state in general).\\
+ \mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(4)] DFAs are defined as a triple: (starting state, transitions,
+ set of accepting 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 resulting state is an accepting state,
+ return \texttt{true}; otherwise \texttt{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 (less restricted) NFA can be translated into
+ an ``equivalent'' DFA, whereby accepting means 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 the NFA
+
+\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 we get an $a$, we can go to state $R_1$
+\emph{or} $R_3$. If we want to find out whether an NFA accepts a
+string, then we need to explore both possibilities. We will do this
+``exploration'' in the tasks below in a breadth-first manner.
+
+
+The feature of having more than one next state in NFAs will be
+implemented by having a \emph{set} of partial transition functions
+(DFAs had only one). 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 makes sure that in state $R_2$ and
+given an $a$, we can go to state $R_1$; and the 4th element, in $R_2$,
+given an $a$, we can also 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 \emph{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, set of accepting states). Write a function
+ \texttt{naccepts} that tests whether a string is accepted by an 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
+ resulting set of states shares at least a single state with the set
+ of accepting states, return \texttt{true}; otherwise \texttt{false}.
+ Use the function under (1) in order to test whether these two sets
+ of states share any states or not.\mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(9)] Since we explore in functions (6) and (7) all possible next
+ states, we decide whether a string is accepted in a breadth-first
+ manner. (Depth-first would be to choose one state, follow all next
+ states of this single state; check whether it leads to an accepting
+ state. If not, we backtrack and choose another state). The
+ disadvantage of breadth-first search is that at every step a
+ non-empty set of states are ``active''\ldots{} states 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, calculate the
+ number of states that need to be followed in each step. The function
+ \texttt{max\_accept} should then return the maximum of all these
+ numbers.
+
+ As a test case, 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 three states of this NFA
+ are active at the same time; is it possible that no state is
+ active?). \hfill\mbox{[2 Marks]}
+
+
+\end{itemize}
+
+
+\end{document}
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End: