\documentclass{article}\usepackage{../style}\usepackage{../langs}\usepackage{../graphics}\begin{document}\section*{Replacement Coursework 2 (Automata)}This coursework is worth 10\%. It is about deterministic andnon-deterministic finite automata. The coursework is due on 21 Marchat 5pm. Make sure the files you submit can be processed by justcalling \texttt{scala <<filename.scala>>}.\bigskip\noindent\textbf{Important:} Do not use any mutable data structures in yoursubmission! They are not needed. This means you cannot use\texttt{ListBuffer}s, for example. Do not use \texttt{return} in yourcode! It has a different meaning in Scala, than in Java. Do not use\texttt{var}! This declares a mutable variable. Make sure thefunctions you submit are defined on the ``top-level'' of Scala, notinside a class or object. Also note that when marking, the running timewill be restricted to a maximum of 360 seconds on my laptop.\subsection*{Disclaimer}It should be understood that the work you submit represents your owneffort! You have not copied from anyone else. An exception is theScala code I showed during the lectures or uploaded to KEATS, whichyou can freely use.\bigskip\subsection*{Part 1 (Deterministic Finite Automata)}\noindentThere are many uses for Deterministic Finite Automata (DFAs), forexample for testing whether a string matches a pattern or not. DFAsconsist of some states (circles) and some transitions (edges) betweenstates. 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}\noindenthas three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is thestarting state of the DFA and $Q_2$ is the accepting state. The latteris indicated by double lines. In general, a DFA can have any number ofaccepting states, but only a single starting state.Transitions are edges between states labelled with a character. Theidea is that if we are in state $Q_0$, say, and get an $a$, we can goto state $Q_1$. If we are in state $Q_2$ and get an $a$, we can stayin 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 acharacter, it is always clear which is the next state---there can onlybe at most one. The task of Part 1 is to implement such DFAs in Scalausing 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 anaccepting state, then the string is accepted. If not, the string isnot accepted. The technical idea is that DFAs can be used toaccept 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 characterthere is at most one next state (one if the transition is defined;none otherwise). However, this restriction to at most one state can bequite 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) removethis restriction: there can be more than one starting state, and givena state and a character there can be more than one nextstate. 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}\noindentwhere 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 astring, 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 beimplemented by having a \emph{set} of partial transition functions(DFAs had only one). For example the NFA shown above will berepresented 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}\noindentThe point is that the 3rd element in this set makes sure that in state $R_2$ andgiven 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 followingtransitions from a state, we have to look at all partial functions inthe 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: