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