\usepackage{../graphics}

\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

submission! They are not needed. This means you cannot use 

\subsection*{Part 1 (Deterministic Finite Automata)}

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}

\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]}

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

\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]}