--- a/cws/cw05.tex Fri Mar 03 14:50:47 2017 +0000
+++ b/cws/cw05.tex Sat Mar 04 14:06:04 2017 +0000
@@ -14,13 +14,13 @@
\noindent
\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This means you cannot use
+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 the running time will be
-restricted to a maximum of 360 seconds on my laptop.
+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}
@@ -35,9 +35,9 @@
\noindent
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
+example for testing whether a string matches a pattern or not. 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,
@@ -57,21 +57,26 @@
\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
+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
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$).
+accepting states, but only a single starting state.
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
+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 we have to 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}
@@ -79,9 +84,12 @@
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
+\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] =
@@ -94,12 +102,12 @@
}
\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
+ 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'))
@@ -107,28 +115,34 @@
\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
+ gives \texttt{true} in the first case and \texttt{false} in the
+ second. There is also a method \texttt{lift} that transformes 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 None).\hfill\mbox{[1 Mark]}
+ 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 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).\\
+ 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: (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]}
+\item[(4)] DFAs are defined as a triple: (staring 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}
@@ -138,12 +152,13 @@
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
+ 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,
@@ -160,14 +175,16 @@
\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
+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 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
+``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(
@@ -179,12 +196,11 @@
\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.
+The point is that the 3rd element in this set states that in $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}
@@ -198,45 +214,45 @@
\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]}
+ 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
+ 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 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]}
+ 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 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.
+\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.
- 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]}
+ 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}