diff -r 3020f8c76baa -r 9e7897f25e13 cws/cw08.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cws/cw08.tex Thu Nov 29 17:15:11 2018 +0000 @@ -0,0 +1,267 @@ +\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 <>}.\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: