cws/cw05.tex
changeset 121 4fc05d4f0e01
parent 119 9bfc82cd3351
--- a/cws/cw05.tex	Fri Mar 10 06:22:30 2017 +0000
+++ b/cws/cw05.tex	Fri Mar 10 23:01:17 2017 +0000
@@ -8,7 +8,7 @@
 \section*{Replacement Coursework 2 (Automata)}
 
 This coursework is worth 10\%. It is about deterministic and
-non-deterministic finite automata.  The coursework is due on ??? March
+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
 
@@ -36,8 +36,8 @@
 \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 transitions (edges) between
-states. For example consider the DFA
+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,
@@ -59,13 +59,13 @@
 \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
-indicated by double lines. In general, a DFA can have any number of
+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 we have to go to state
+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
@@ -109,14 +109,14 @@
   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]
+\begin{lstlisting}[language=Scala,numbers=none]
     dfa_trans.isDefinedAt((Q0, 'a'))
     dfa_trans.isDefinedAt((Q0, 'c'))
-  \end{lstlisting}   
+\end{lstlisting}   
 
   \noindent
   gives \texttt{true} in the first case and \texttt{false} in the
-  second.  There is also a method \texttt{lift} that transformes a
+  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
@@ -136,7 +136,7 @@
   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,
+\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
@@ -196,7 +196,7 @@
 \end{lstlisting}
 
 \noindent
-The point is that the 3rd element in this set states that in $R_2$ and
+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