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