\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: