--- a/cws/cw08.tex	Fri Apr 26 17:29:30 2024 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,267 +0,0 @@
-\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: