
diff -r 4430477595ec -r 8a07f7256f2a handouts/ho03.tex
--- a/handouts/ho03.tex	Sun May 07 03:01:29 2017 +0100
+++ b/handouts/ho03.tex	Tue May 09 12:31:55 2017 +0100
@@ -40,7 +40,7 @@
 \item $\delta$ is the transition function.
 \end{itemize}
 
-\noindent I am sure you have seen this defininition already
+\noindent I am sure you have seen this definition already
 before. The transition function determines how to ``transition'' from
 one state to the next state with respect to a character. We have the
 assumption that these transition functions do not need to be defined
@@ -122,13 +122,11 @@
 \]
 
 \noindent I let you think about a definition that describes the set of
-all strings accepted by a determinsitic finite automaton.
+all strings accepted by a deterministic finite automaton.
 
 \begin{figure}[p]
 \small
-\lstinputlisting[numbers=left,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
-                  {../progs/display/dfa.scala}
+\lstinputlisting[numbers=left]{../progs/display/dfa.scala}
 \caption{A Scala implementation of DFAs using partial functions.
   Note some subtleties: \texttt{deltas} implements the delta-hat
   construction by lifting the (partial) transition  function to lists
@@ -171,8 +169,7 @@
 sink state (catch-all-state), you can use Scala's pattern matching and
 write something like
 
-{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{\small\begin{lstlisting}[language=Scala]
 abstract class State
 ...
 case object Sink extends State
@@ -267,8 +264,7 @@
 mathematical definition of NFAs. An example of a transition function
 in Scala for the NFA shown above is
 
-{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{\small\begin{lstlisting}[language=Scala]
 val nfa_delta : (State, Char) :=> Set[State] = 
   { case (Q0, 'a') => Set(Q1, Q2)
     case (Q0, 'b') => Set(Q0)
@@ -276,7 +272,7 @@
     case (Q1, 'b') => Set(Q0, Q1) }
 \end{lstlisting}}  
 
-\noindent Like in the mathematical definition, \texttt{starts} is in
+Like in the mathematical definition, \texttt{starts} is in
 NFAs a set of states; \texttt{fins} is again a function from states to
 booleans. The \texttt{next} function calculates the set of next states
 reachable from a single state \texttt{q} by a character~\texttt{c}. In
@@ -287,9 +283,7 @@
  
 \begin{figure}[p]
 \small
-\lstinputlisting[numbers=left,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
-                  {../progs/display/nfa.scala}
+\lstinputlisting[numbers=left]{../progs/display/nfa.scala}
 \caption{A Scala implementation of NFAs using partial functions.
   Notice that the function \texttt{accepts} implements the
   acceptance of a string in a breath-first search fashion. This can be a costly
@@ -311,8 +305,7 @@
 \texttt{accepts} using Scala's \texttt{exists}-function as follows:
 
 
-{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{\small\begin{lstlisting}[language=Scala]
 def search(q: A, s: List[C]) : Boolean = s match {
   case Nil => fins(q)
   case c::cs => next(q, c).exists(search(_, cs)) 
@@ -332,7 +325,7 @@
 Ruby and Python. I like to show you this in the next two sections.
 
 
-\subsubsection*{Epsilon NFAs}
+\subsection*{Epsilon NFAs}
 
 In order to get an idea what calculations are performed by Java \&
 friends, we need a method for transforming a regular expression into
@@ -389,7 +382,7 @@
 this example, if you are in the starting state $Q_0$, you can silently
 move either to $Q_1$ or $Q_2$. You can see that once you are in $Q_1$,
 respectively $Q_2$, you cannot ``go back'' to the other states. So it
-seems allowing $\epsilon$-transitions is a rather substancial
+seems allowing $\epsilon$-transitions is a rather substantial
 extension to NFAs. On first appearances, $\epsilon$-transitions might
 even look rather strange, or even silly. To start with, silent
 transitions make the decision whether a string is accepted by an
@@ -407,7 +400,7 @@
 unfortunately.  If we were to follow the many textbooks on the
 subject, we would now start with defining what $\epsilon$NFAs
 are---that would require extending the transition relation of
-NFAs. Next, we woudl show that the $\epsilon$NFAs are equivalent to
+NFAs. Next, we would show that the $\epsilon$NFAs are equivalent to
 NFAs and so on. Once we have done all this on paper, we would need to
 implement $\epsilon$NFAs. Lets try to take a shortcut instead. We are
 not really interested in $\epsilon$NFAs; they are only a convenient
@@ -464,12 +457,10 @@
 
 \begin{figure}[p]
 \small
-\lstinputlisting[numbers=left,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
-                  {../progs/display/enfa.scala}
+\lstinputlisting[numbers=left]{../progs/display/enfa.scala}
 
 \caption{A Scala function that translates $\epsilon$NFA into NFAs. The
-  transtion function of $\epsilon$NFA takes as input an \texttt{Option[C]}.
+  transition function of $\epsilon$NFA takes as input an \texttt{Option[C]}.
   \texttt{None} stands for an $\epsilon$-transition; \texttt{Some(c)}
   for a ``proper'' transition consuming a character. The functions in
   Lines 18--26 calculate
@@ -480,13 +471,12 @@
 Also look carefully how the transitions of $\epsilon$NFAs are
 implemented. The additional possibility of performing silent
 transitions is encoded by using \texttt{Option[C]} as the type for the
-``input''. The \texttt{Some}s stand for ``propper'' transitions where
+``input''. The \texttt{Some}s stand for ``proper'' transitions where
 a character is consumed; \texttt{None} stands for
 $\epsilon$-transitions. The transition functions for the two
 $\epsilon$NFAs from the beginning of this section can be defined as
 
-{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{\small\begin{lstlisting}[language=Scala]
 val enfa_trans1 : (State, Option[Char]) :=> Set[State] = 
   { case (Q0, Some('a')) => Set(Q0)
     case (Q0, None) => Set(Q1, Q2)
@@ -503,7 +493,7 @@
 I hope you agree now with my earlier statement that the $\epsilon$NFAs
 are just an API for NFAs.
 
-\subsubsection*{Thompson Construction}
+\subsection*{Thompson Construction}
 
 Having the translation of $\epsilon$NFAs to NFAs in place, we can
 finally return to the problem of translating regular expressions into
@@ -543,9 +533,7 @@
 
 \begin{figure}[p]
 \small
-\lstinputlisting[numbers=left,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
-                  {../progs/display/thompson1.scala}
+\lstinputlisting[numbers=left]{../progs/display/thompson1.scala}
 \caption{The first part of the Thompson Construction. Lines 7--16
   implement a way of how to create new states that are all
   distinct by virtue of a counter. This counter is
@@ -558,11 +546,9 @@
 
 \begin{figure}[p]
 \small
-\lstinputlisting[numbers=left,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
-                  {../progs/display/thompson2.scala}
+\lstinputlisting[numbers=left]{../progs/display/thompson2.scala}
 \caption{The second part of the Thompson Construction implementing
-  the composition of NFAs according to $\cdot$, $+$ and $\_^*$.
+  the composition of NFAs according to $\cdot$, $+$ and ${}^*$.
   The implicit class about rich partial functions
   implements the infix operation \texttt{+++} which
   combines an $\epsilon$NFA transition with a NFA transition
@@ -650,25 +636,31 @@
 string is first recognised by the first NFA, then we silently change
 to the second NFA; the ending of the string is recognised by the
 second NFA...just like matching of a string by the regular expression
-$r_1\cdot r_2$. The Scala code for this constrction is given in
+$r_1\cdot r_2$. The Scala code for this construction is given in
 Figure~\ref{thompson2} in Lines 16--23. The starting states of the
 $\epsilon$NFA are the starting states of the first NFA (corresponding
 to $r_1$); the accepting function is the accepting function of the
 second NFA (corresponding to $r_2$). The new transition function is
 all the ``old'' transitions plus the $\epsilon$-transitions connecting
 the accepting states of the first NFA to the starting states of the
-first NFA (Lines 18 and 19). The $\epsilon$NFA is then immedately
+first NFA (Lines 18 and 19). The $\epsilon$NFA is then immediately
 translated in a NFA.
 
 
-The case for the choice regular expression $r_1 + r_2$ is slightly
-different: We are given by recursion two NFAs representing $r_1$ and
-$r_2$ respectively.
+The case for the alternative regular expression $r_1 + r_2$ is
+slightly different: We are given by recursion two NFAs representing
+$r_1$ and $r_2$ respectively. Each NFA has some starting states and
+some accepting states. We obtain a NFA for the regular expression $r_1
++ r_2$ by composing the transition functions (this crucially depends
+on knowing that the states of each component NFA are distinct); and
+also combine the starting states and accepting functions.
 
 \begin{center}
+\begin{tabular}[t]{ccc}
 \begin{tikzpicture}[node distance=3mm,
     >=stealth',very thick,
-    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.center)]
 \node at (0,0)  (1)  {$\mbox{}$};
 \node  (2)  [above=10mm of 1] {};
 \node[state, initial]  (4)  [above=1mm of 2] {$\mbox{}$};
@@ -691,18 +683,13 @@
 \node [yshift=3mm] at (2.north) {$r_2$};
 \end{pgfonlayer}
 \end{tikzpicture}
-\end{center}
-
-\noindent Each NFA has some starting states and some accepting
-states. We obtain a NFA for the regular expression $r_1 + r_2$
-by composing the transition functions (this crucially depends
-on knowing that the states of each component NFA are distinct);
-and also combine the starting states and accepting functions:
-
-\begin{center}
+&
+\mbox{}\qquad\tikz{\draw[>=stealth,line width=2mm,->] (0,0) -- (1, 0)}\quad\mbox{}
+&
 \begin{tikzpicture}[node distance=3mm,
     >=stealth',very thick,
-    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.center)]
 \node at (0,0) (1)  {$\mbox{}$};
 \node (2)  [above=10mm of 1] {$$};
 \node[state, initial]  (4)  [above=1mm of 2] {$\mbox{}$};
@@ -727,14 +714,23 @@
 \node [yshift=3mm] at (3.north) {$r_1+ r_2$};
 \end{pgfonlayer}
 \end{tikzpicture}
+\end{tabular}
 \end{center}
 
 \noindent The code for this construction is in Figure~\ref{thompson2}
-in Lines 25--33. Finally for the $*$-case we have a NFA for $r$
+in Lines 25--33.
+
+Finally for the $*$-case we have a NFA for $r$ and connect its
+accepting states to a new starting state via
+$\epsilon$-transitions. This new starting state is also an accepting
+state, because $r^*$ can recognise the empty string.
 
 \begin{center}
+\begin{tabular}[b]{@{\hspace{-4mm}}ccc@{}}  
 \begin{tikzpicture}[node distance=3mm,
-                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+    >=stealth',very thick,
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.north)]
 \node at (0,0)  (1)  {$\mbox{}$};
 \node[state, initial]  (2)  [right=16mm of 1] {$\mbox{}$};
 \node (a)  [right=of 2] {$\ldots$};
@@ -746,18 +742,13 @@
 \node [yshift=3mm] at (1.north) {$r$};
 \end{pgfonlayer}
 \end{tikzpicture}
-\end{center}
-
-\noindent and connect its accepting states to a new starting state via
-$\epsilon$-transitions. This new starting state is also an accepting
-state, because $r^*$ can recognise the empty string. This gives the
-following $\epsilon$NFA for $r^*$ (the corresponding code is in
-Figure~\ref{thompson2} in Lines 35--43:
-
-\begin{center}  
+&
+\raisebox{-16mm}{\;\tikz{\draw[>=stealth,line width=2mm,->] (0,0) -- (1, 0)}}
+&
 \begin{tikzpicture}[node distance=3mm,
     >=stealth',very thick,
-    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
+    every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+    baseline=(current bounding box.north)]
 \node at (0,0) [state, initial,accepting]  (1)  {$\mbox{}$};
 \node[state]  (2)  [right=16mm of 1] {$\mbox{}$};
 \node (a)  [right=of 2] {$\ldots$};
@@ -772,21 +763,23 @@
 \node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
 \node [yshift=3mm] at (2.north) {$r^*$};
 \end{pgfonlayer}
-\end{tikzpicture}
+\end{tikzpicture}    
+\end{tabular}
 \end{center}
 
+\noindent 
+The corresponding code is in Figure~\ref{thompson2} in Lines 35--43)
 
-To sum ap, you can see in the sequence and star cases the need of
+To sum up, you can see in the sequence and star cases the need of
 having silent $\epsilon$-transitions. Similarly the alternative case
-shows the need of the NFA-nondeterminsim. It seems awkward to form the
+shows the need of the NFA-nondeterminism. It seems awkward to form the
 `alternative' composition of two DFAs, because DFA do not allow
 several starting and successor states. All these constructions can now
 be put together in the following recursive function:
 
 
-{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=
-                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]
-def thompson (r: Rexp) : NFAt = r match {
+{\small\begin{lstlisting}[language=Scala]
+def thompson(r: Rexp) : NFAt = r match {
   case ZERO => NFA_ZERO()
   case ONE => NFA_ONE()
   case CHAR(c) => NFA_CHAR(c)  
@@ -797,16 +790,25 @@
 \end{lstlisting}}
 
 \noindent
-It calculates a NFA from a regular expressions. At last we can run a
-NFA for the our evil regular expression examples.
+It calculates a NFA from a regular expressions. At last we can run
+NFAs for the our evil regular expression examples.  The graph on the
+left shows that when translating a regular expression such as
+$a^{\{n\}}$ into a NFA, the size can blow up and then even the
+relative fast (on small examples) breadth-first search can be
+slow. The graph on the right shows that with `evil' regular
+expressions the depth-first search can be abysmally slow. Even if the
+graphs not completely overlap with the curves of Python, Ruby and
+Java, they are similar enough. OK\ldots now you know why regular
+expression matchers in those languages are so slow. 
 
 
 \begin{center}
 \begin{tabular}{@{\hspace{-1mm}}c@{\hspace{1mm}}c@{}}  
 \begin{tikzpicture}
 \begin{axis}[
-    title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings 
+    title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings 
            $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+    title style={yshift=-2ex},
     xlabel={$n$},
     x label style={at={(1.05,0.0)}},
     ylabel={time in secs},
@@ -818,9 +820,9 @@
     scaled ticks=false,
     axis lines=left,
     width=5.5cm,
-    height=4.5cm, 
-    legend entries={Python,Ruby},  
-    legend pos=south east,
+    height=4cm, 
+    legend entries={Python,Ruby, breadth-first NFA},
+    legend style={at={(0.5,-0.25)},anchor=north,font=\small},
     legend cell align=left]
   \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
   \addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
@@ -845,8 +847,9 @@
 &
 \begin{tikzpicture}
 \begin{axis}[
-    title={Graph: $\texttt{(a*)*\,b}$ and strings 
+    title={Graph: $(a^*)^* \cdot b$ and strings 
            $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+    title style={yshift=-2ex},
     xlabel={$n$},
     x label style={at={(1.05,0.0)}},
     ylabel={time in secs},
@@ -858,9 +861,9 @@
     scaled ticks=false,
     axis lines=left,
     width=5.5cm,
-    height=4.5cm, 
-    legend entries={Python, Java},  
-    legend pos=outer north east,
+    height=4cm, 
+    legend entries={Python, Java, depth-first NFA},
+    legend style={at={(0.5,-0.25)},anchor=north,font=\small},
     legend cell align=left]
   \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
   \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};  
@@ -881,166 +884,318 @@
 
 
 
-\subsubsection*{Subset Construction}
+\subsection*{Subset Construction}
+
+Of course, some developers of regular expression matchers are aware
+of these problems with sluggish NFAs and try to address them. One
+common technique for this I like to show you in this section. It will
+also explain why we insisted on polymorphic types in our DFA code
+(remember I used \texttt{A} and \texttt{C} for the types of states and
+the input, see Figure~\ref{dfa} on Page~\pageref{dfa}).\bigskip
 
-Remember that we did not bother with defining and implementing
-$\epsilon$NFA; we immediately translated them into equivalent
-NFAs. Equivalent in the sense of accepting the same language (though
-we only claimed this and did not prove it rigorously). Remember also
-that NFAs have a non-deterministic transitions, given as a relation.
-This non-determinism makes it harder to decide when a string is
-accepted or not; such a decision is rather straightforward with DFAs
-(remember their transition function).
+\noindent
+To start, remember that we did not bother with defining and
+implementing $\epsilon$NFA; we immediately translated them into
+equivalent NFAs. Equivalent in the sense of accepting the same
+language (though we only claimed this and did not prove it
+rigorously). Remember also that NFAs have non-deterministic
+transitions defined as a relation or implemented as function returning
+sets of states.  This non-determinism is crucial for the Thompson
+Construction to work (recall the cases for $\cdot$, $+$ and
+${}^*$). But this non-determinism makes it harder with NFAs to decide
+when a string is accepted or not; such a decision is rather
+straightforward with DFAs: recall their transition function is a
+\emph{function} that returns a single state. So we do not have to
+search at all.  What is perhaps interesting is the fact that for every
+NFA we can find a DFA that also recognises the same language. This
+might sound a bit paradoxical: NFA $\rightarrow$ decision of
+acceptance hard; DFA $\rightarrow$ decision easy. But this \emph{is}
+true\ldots but of course there is always a caveat---nothing is ever
+for free in life.
 
-What is interesting is that for every NFA we can find a DFA that also
-recognises the same language. This might sound like a bit paradoxical,
-but I litke to show you this next. There are a number of ways of
-transforming a NFA into an equivalent DFA, but the most famous is
-\emph{subset construction}. Consider again the NFA below on the left,
-consisting of nodes labelled, say, with $0$, $1$ and $2$.
+There are a number of techniques for transforming a NFA into an
+equivalent DFA, but the most famous one is the \emph{subset
+  construction}. Consider the following NFA where the states are
+labelled with, say, $0$, $1$ and $2$.
 
 \begin{center}
 \begin{tabular}{c@{\hspace{10mm}}c}
 \begin{tikzpicture}[scale=0.7,>=stealth',very thick,
                     every state/.style={minimum size=0pt,
                     draw=blue!50,very thick,fill=blue!20},
-                    baseline=0mm]
+                    baseline=(current bounding box.center)]
 \node[state,initial]  (Q_0)  {$0$};
-\node[state] (Q_1) [above=of Q_0] {$1$};
-\node[state, accepting] (Q_2) [below=of Q_0] {$2$};
-\path[->] (Q_0) edge node [left]  {$\epsilon$} (Q_1);
-\path[->] (Q_0) edge node [left]  {$\epsilon$} (Q_2);
-\path[->] (Q_0) edge [loop right] node  {$a$} ();
-\path[->] (Q_1) edge [loop above] node  {$a$} ();
-\path[->] (Q_2) edge [loop below] node  {$b$} ();
+\node[state] (Q_1) [below=of Q_0] {$1$};
+\node[state, accepting] (Q_2) [below=of Q_1] {$2$};
+
+\path[->] (Q_0) edge node [right]  {$b$} (Q_1);
+\path[->] (Q_1) edge node [right]  {$a,b$} (Q_2);
+\path[->] (Q_0) edge [loop above] node  {$a, b$} ();
 \end{tikzpicture}
 &
-\begin{tabular}{r|cl}
-nodes & $a$ & $b$\\
+\begin{tabular}{r|ll}
+states & $a$ & $b$\\
 \hline
 $\{\}\phantom{\star}$ & $\{\}$ & $\{\}$\\
-$\{0\}\phantom{\star}$       & $\{0,1,2\}$   & $\{2\}$\\
-$\{1\}\phantom{\star}$       & $\{1\}$       & $\{\}$\\
-$\{2\}\star$  & $\{\}$ & $\{2\}$\\
-$\{0,1\}\phantom{\star}$     & $\{0,1,2\}$   & $\{2\}$\\
-$\{0,2\}\star$ & $\{0,1,2\}$   & $\{2\}$\\
-$\{1,2\}\star$ & $\{1\}$       & $\{2\}$\\
-s: $\{0,1,2\}\star$ & $\{0,1,2\}$ & $\{2\}$\\
+start: $\{0\}\phantom{\star}$       & $\{0\}$   & $\{0,1\}$\\
+$\{1\}\phantom{\star}$       & $\{2\}$       & $\{2\}$\\
+$\{2\}\star$  & $\{\}$ & $\{\}$\\
+$\{0,1\}\phantom{\star}$     & $\{0,2\}$   & $\{0,1,2\}$\\
+$\{0,2\}\star$ & $\{0\}$   & $\{0,1\}$\\
+$\{1,2\}\star$ & $\{2\}$       & $\{2\}$\\
+$\{0,1,2\}\star$ & $\{0,2\}$ & $\{0,1,2\}$\\
 \end{tabular}
 \end{tabular}
 \end{center}
 
-\noindent The nodes of the DFA are given by calculating all
-subsets of the set of nodes of the NFA (seen in the nodes
-column on the right). The table shows the transition function
-for the DFA. The first row states that $\{\}$ is the
-sink node which has transitions for $a$ and $b$ to itself.
-The next three lines are calculated as follows: 
+\noindent The states of the corresponding DFA are given by generating
+all subsets of the set of states of the NFA (seen in the states column
+in the table on the right). The other columns define the transition
+function for the DFA for input $a$ and $b$. The first row states that
+$\{\}$ is the sink state which has transitions for $a$ and $b$ to
+itself.  The next three lines are calculated as follows:
 
 \begin{itemize}
-\item suppose you calculate the entry for the transition for
-      $a$ and the node $\{0\}$
-\item start from the node $0$ in the NFA
-\item do as many $\epsilon$-transition as you can obtaining a
-      set of nodes, in this case $\{0,1,2\}$
-\item filter out all notes that do not allow an $a$-transition
-      from this set, this excludes $2$ which does not permit a
-      $a$-transition
-\item from the remaining set, do as many $\epsilon$-transition
-      as you can, this yields again $\{0,1,2\}$     
-\item the resulting set specifies the transition from $\{0\}$
-      when given an $a$ 
+\item Suppose you calculate the entry for the $a$-transition for state
+  $\{0\}$. Look for all states in the NFA that can be reached by such
+  a transition from this state; this is only state $0$; therefore from
+  state $\{0\}$ we can go to state $\{0\}$ via an $a$-transition.
+\item Do the same for the $b$-transition; you can reach states $0$ and
+  $1$ in the NFA; therefore in the DFA we can go from state $\{0\}$ to
+  state $\{0,1\}$ via an $b$-transition.
+\item Continue with the states $\{1\}$ and $\{2\}$.
+\item Once you filled in the transitions for `simple' state, you only
+  have to build the union for the compound states $\{0,1\}$, $\{0,2\}$
+  and so on. For example for $\{0,1\}$ you take the union of line
+  $\{0\}$ and line $\{1\}$, which gives $\{0,2\}$ for $a$, and
+  $\{0,1,2\}$ for $b$. And so on.
+\item The starting state of the DFA can be calculated from the
+  starting states of the NFA, that is in this case $0$. But in general
+  there can be many starting states in the NFA and you would take the
+  corresponding subset as \emph{the} starting state of the DFA.
+\item The accepting states in the DFA are given by all sets that
+  contain a $2$, which is the only accpting state in this NFA. But
+  again in general if the subset contains an accepting state from the
+  NFA, then the corresponding state in the DFA is accepting as well.
 \end{itemize}
 
-\noindent So the transition from the state $\{0\}$ reading an
-$a$ goes to the state $\{0,1,2\}$. Similarly for the other
-entries in the rows for $\{0\}$, $\{1\}$ and $\{2\}$. The
-other rows are calculated by just taking the union of the
-single node entries. For example for $a$ and $\{0,1\}$ we need
-to take the union of $\{0,1,2\}$ (for $0$) and $\{1\}$ (for
-$1$). The starting state of the DFA can be calculated from the
-starting state of the NFA, that is $0$, and then do as many
-$\epsilon$-transitions as possible. This gives $\{0,1,2\}$
-which is the starting state of the DFA. The terminal states in
-the DFA are given by all sets that contain a $2$, which is the
-terminal state of the NFA. This completes the subset
-construction. So the corresponding DFA to the NFA from 
-above is
+\noindent This completes the subset construction. The corresponding
+DFA for the NFA shown above is:
 
 \begin{center}
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+\begin{tikzpicture}[scale=0.8,>=stealth',very thick,
                     every state/.style={minimum size=0pt,
                     draw=blue!50,very thick,fill=blue!20},
                     baseline=0mm]
-\node[state,initial,accepting]  (q012)  {$0,1,2$};
-\node[state,accepting] (q02) [right=of q012] {$0,2$};
-\node[state] (q01) [above=of q02] {$0,1$};
-\node[state,accepting] (q12) [below=of q02] {$1,2$};
-\node[state] (q0) [right=2cm of q01] {$0$};
-\node[state] (q1) [right=2.5cm of q02] {$1$};
-\node[state,accepting] (q2) [right=1.5cm of q12] {$2$};
-\node[state] (qn) [right=of q1] {$\{\}$};
+\node[state,initial]  (q0)  {$0$};
+\node[state] (q01) [right=of q0] {$0,1$};
+\node[state,accepting] (q02) [below=of q01] {$0,2$};
+\node[state,accepting] (q012) [right=of q02] {$0,1,2$};
+\node[state] (q1) [below=0.5cm of q0] {$1$};
+\node[state,accepting] (q2) [below=1cm of q1] {$2$};
+\node[state] (qn) [below left=1cm of q2] {$\{\}$};
+\node[state,accepting] (q12) [below right=1cm of q2] {$1,2$};
+
+\path[->] (q0) edge node [above] {$b$} (q01);
+\path[->] (q01) edge node [above] {$b$} (q012);
+\path[->] (q0) edge [loop above] node  {$a$} ();
+\path[->] (q012) edge [loop right] node  {$b$} ();
+\path[->] (q012) edge node [below] {$a$} (q02);
+\path[->] (q02) edge node [below] {$a$} (q0);
+\path[->] (q01) edge [bend left] node [left]  {$a$} (q02);
+\path[->] (q02) edge [bend left] node [right]  {$b$} (q01);
+\path[->] (q1) edge node [left] {$a,b$} (q2);
+\path[->] (q12) edge node [right] {$a, b$} (q2);
+\path[->] (q2) edge node [right] {$a, b$} (qn);
+\path[->] (qn) edge [loop left] node  {$a,b$} ();
+\end{tikzpicture}
+\end{center}
+
+\noindent
+Please check that this is indeed a DFA. The big question is whether
+this DFA can recognise the same language as the NFA we started with.
+I let you ponder about this question.
+
+
+There are also two points to note: One is that very often the
+resulting DFA contains a number of ``dead'' states that are never
+reachable from the starting state. This is obvious in this case, where
+state $\{1\}$, $\{2\}$, $\{1,2\}$ and $\{\}$ can never be reached from
+the starting state.  In effect the DFA in this example is not a
+\emph{minimal} DFA (more about this in a minute). Such dead states can
+be safely removed without changing the language that is recognised by
+the DFA. Another point is that in some cases, however, the subset
+construction produces a DFA that does \emph{not} contain any dead
+states\ldots{}and further calculates a minimal DFA. Which in turn
+means that in some cases the number of states can by going from NFAs
+to DFAs exponentially increase, namely by $2^n$ (which is the number
+of subsets you can form for $n$ states).  This blow up the number of
+states in the DFA is again bad news for how quickly you can decide
+whether a string is accepted by a DFA or not. So the caveat with DFAs
+is that they might make the task of finding the next state trival, but
+might require $2^n$ times as many states as a NFA.\bigskip
+
+Lastly, can we 
+
+{\small\begin{lstlisting}[language=Scala]
+def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {
+  DFA(nfa.starts, 
+      { case (qs, c) => nfa.nexts(qs, c) }, 
+      _.exists(nfa.fins))
+}
+\end{lstlisting}}  
+
+
+
+\subsection*{DFA Minimisation}
+
+As seen in the subset construction, the translation 
+of a NFA to a DFA can result in a rather ``inefficient'' 
+DFA. Meaning there are states that are not needed. A
+DFA can be \emph{minimised} by the following algorithm:
+
+\begin{enumerate}
+\item Take all pairs $(q, p)$ with $q \not= p$
+\item Mark all pairs that accepting and non-accepting states
+\item For all unmarked pairs $(q, p)$ and all characters $c$
+      test whether 
+      
+      \begin{center} 
+      $(\delta(q, c), \delta(p,c))$ 
+      \end{center} 
+      
+      are marked. If there is one, then also mark $(q, p)$.
+\item Repeat last step until no change.
+\item All unmarked pairs can be merged.
+\end{enumerate}
+
+\noindent To illustrate this algorithm, consider the following 
+DFA.
 
-\path[->] (q012) edge [loop below] node  {$a$} ();
-\path[->] (q012) edge node [above]  {$b$} (q2);
-\path[->] (q12) edge [bend left] node [below,pos=0.4]  {$a$} (q1);
-\path[->] (q12) edge node [below]  {$b$} (q2);
-\path[->] (q02) edge node [above]  {$a$} (q012);
-\path[->] (q02) edge [bend left] node [above, pos=0.8]  {$b$} (q2);
-\path[->] (q01) edge node [below]  {$a$} (q012);
-\path[->] (q01) edge [bend left] node [above]  {$b$} (q2);
-\path[->] (q0) edge node [below]  {$a$} (q012);
-\path[->] (q0) edge node [right, pos=0.2]  {$b$} (q2);
-\path[->] (q1) edge [loop above] node  {$a$} ();
-\path[->] (q1) edge node [above]  {$b$} (qn);
-\path[->] (q2) edge [loop right] node  {$b$} ();
-\path[->] (q2) edge node [below]  {$a$} (qn);
-\path[->] (qn) edge [loop above] node  {$a,b$} ();
+\begin{center}
+\begin{tikzpicture}[>=stealth',very thick,auto,
+                    every state/.style={minimum size=0pt,
+                    inner sep=2pt,draw=blue!50,very thick,
+                    fill=blue!20}]
+\node[state,initial]  (Q_0)  {$Q_0$};
+\node[state] (Q_1) [right=of Q_0] {$Q_1$};
+\node[state] (Q_2) [below right=of Q_0] {$Q_2$};
+\node[state] (Q_3) [right=of Q_2] {$Q_3$};
+\node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$};
+\path[->] (Q_0) edge node [above]  {$a$} (Q_1);
+\path[->] (Q_1) edge node [above]  {$a$} (Q_4);
+\path[->] (Q_4) edge [loop right] node  {$a, b$} ();
+\path[->] (Q_3) edge node [right]  {$a$} (Q_4);
+\path[->] (Q_2) edge node [above]  {$a$} (Q_3);
+\path[->] (Q_1) edge node [right]  {$b$} (Q_2);
+\path[->] (Q_0) edge node [above]  {$b$} (Q_2);
+\path[->] (Q_2) edge [loop left] node  {$b$} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node 
+  [below]  {$b$} (Q_0);
+\end{tikzpicture}
+\end{center}
+
+\noindent In Step 1 and 2 we consider essentially a triangle
+of the form
+
+\begin{center}
+\begin{tikzpicture}[scale=0.6,line width=0.8mm]
+\draw (0,0) -- (4,0);
+\draw (0,1) -- (4,1);
+\draw (0,2) -- (3,2);
+\draw (0,3) -- (2,3);
+\draw (0,4) -- (1,4);
+
+\draw (0,0) -- (0, 4);
+\draw (1,0) -- (1, 4);
+\draw (2,0) -- (2, 3);
+\draw (3,0) -- (3, 2);
+\draw (4,0) -- (4, 1);
+
+\draw (0.5,-0.5) node {$Q_0$}; 
+\draw (1.5,-0.5) node {$Q_1$}; 
+\draw (2.5,-0.5) node {$Q_2$}; 
+\draw (3.5,-0.5) node {$Q_3$};
+ 
+\draw (-0.5, 3.5) node {$Q_1$}; 
+\draw (-0.5, 2.5) node {$Q_2$}; 
+\draw (-0.5, 1.5) node {$Q_3$}; 
+\draw (-0.5, 0.5) node {$Q_4$}; 
+
+\draw (0.5,0.5) node {\large$\star$}; 
+\draw (1.5,0.5) node {\large$\star$}; 
+\draw (2.5,0.5) node {\large$\star$}; 
+\draw (3.5,0.5) node {\large$\star$};
+\end{tikzpicture}
+\end{center}
+
+\noindent where the lower row is filled with stars, because in
+the corresponding pairs there is always one state that is
+accepting ($Q_4$) and a state that is non-accepting (the other
+states).
+
+Now in Step 3 we need to fill in more stars according whether 
+one of the next-state pairs are marked. We have to do this 
+for every unmarked field until there is no change anymore.
+This gives the triangle
+
+\begin{center}
+\begin{tikzpicture}[scale=0.6,line width=0.8mm]
+\draw (0,0) -- (4,0);
+\draw (0,1) -- (4,1);
+\draw (0,2) -- (3,2);
+\draw (0,3) -- (2,3);
+\draw (0,4) -- (1,4);
+
+\draw (0,0) -- (0, 4);
+\draw (1,0) -- (1, 4);
+\draw (2,0) -- (2, 3);
+\draw (3,0) -- (3, 2);
+\draw (4,0) -- (4, 1);
+
+\draw (0.5,-0.5) node {$Q_0$}; 
+\draw (1.5,-0.5) node {$Q_1$}; 
+\draw (2.5,-0.5) node {$Q_2$}; 
+\draw (3.5,-0.5) node {$Q_3$};
+ 
+\draw (-0.5, 3.5) node {$Q_1$}; 
+\draw (-0.5, 2.5) node {$Q_2$}; 
+\draw (-0.5, 1.5) node {$Q_3$}; 
+\draw (-0.5, 0.5) node {$Q_4$}; 
+
+\draw (0.5,0.5) node {\large$\star$}; 
+\draw (1.5,0.5) node {\large$\star$}; 
+\draw (2.5,0.5) node {\large$\star$}; 
+\draw (3.5,0.5) node {\large$\star$};
+\draw (0.5,1.5) node {\large$\star$}; 
+\draw (2.5,1.5) node {\large$\star$}; 
+\draw (0.5,3.5) node {\large$\star$}; 
+\draw (1.5,2.5) node {\large$\star$}; 
+\end{tikzpicture}
+\end{center}
+
+\noindent which means states $Q_0$ and $Q_2$, as well as $Q_1$
+and $Q_3$ can be merged. This gives the following minimal DFA
+
+\begin{center}
+\begin{tikzpicture}[>=stealth',very thick,auto,
+                    every state/.style={minimum size=0pt,
+                    inner sep=2pt,draw=blue!50,very thick,
+                    fill=blue!20}]
+\node[state,initial]  (Q_02)  {$Q_{0, 2}$};
+\node[state] (Q_13) [right=of Q_02] {$Q_{1, 3}$};
+\node[state, accepting] (Q_4) [right=of Q_13] 
+  {$Q_{4\phantom{,0}}$};
+\path[->] (Q_02) edge [bend left] node [above]  {$a$} (Q_13);
+\path[->] (Q_13) edge [bend left] node [below]  {$b$} (Q_02);
+\path[->] (Q_02) edge [loop below] node  {$b$} ();
+\path[->] (Q_13) edge node [above]  {$a$} (Q_4);
+\path[->] (Q_4) edge [loop above] node  {$a, b$} ();
 \end{tikzpicture}
 \end{center}
 
 
-
-There are two points to note: One is that very often the
-resulting DFA contains a number of ``dead'' nodes that are
-never reachable from the starting state. For example
-there is no way to reach node $\{0,2\}$ from the starting
-state $\{0,1,2\}$. I let you find the other dead states.
-In effect the DFA in this example is not a minimal DFA. Such
-dead nodes can be safely removed without changing the language
-that is recognised by the DFA. Another point is that in some
-cases, however, the subset construction produces a DFA that
-does \emph{not} contain any dead nodes\ldots{}that means it
-calculates a minimal DFA. Which in turn means that in some
-cases the number of nodes by going from NFAs to DFAs
-exponentially increases, namely by $2^n$ (which is the number
-of subsets you can form for $n$ nodes). 
-
-Removing all the dead states in the automaton above,
-gives a much more legible automaton, namely
-
-\begin{center}
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
-                    every state/.style={minimum size=0pt,
-                    draw=blue!50,very thick,fill=blue!20},
-                    baseline=0mm]
-\node[state,initial,accepting]  (q012)  {$0,1,2$};
-\node[state,accepting] (q2) [right=of q012] {$2$};
-\node[state] (qn) [right=of q2] {$\{\}$};
-
-\path[->] (q012) edge [loop below] node  {$a$} ();
-\path[->] (q012) edge node [above]  {$b$} (q2);
-\path[->] (q2) edge [loop below] node  {$b$} ();
-\path[->] (q2) edge node [below]  {$a$} (qn);
-\path[->] (qn) edge [loop above] node  {$a,b$} ();
-\end{tikzpicture}
-\end{center}
-
-\noindent Now the big question is whether this DFA
-can recognise the same language as the NFA we started with.
-I let you ponder about this question.
-
-\subsubsection*{Brzozowski's Method}
+\subsection*{Brzozowski's Method}
 
 As said before, we can also go into the other direction---from
 DFAs to regular expressions. Brzozowski's method calculates
@@ -1190,154 +1345,8 @@
 an equivalent  regular expression for the automaton. But
 for the purposes of this module, we omit this.
 
-\subsubsection*{Automata Minimization}
 
-As seen in the subset construction, the translation 
-of a NFA to a DFA can result in a rather ``inefficient'' 
-DFA. Meaning there are states that are not needed. A
-DFA can be \emph{minimised} by the following algorithm:
-
-\begin{enumerate}
-\item Take all pairs $(q, p)$ with $q \not= p$
-\item Mark all pairs that accepting and non-accepting states
-\item For all unmarked pairs $(q, p)$ and all characters $c$
-      test whether 
-      
-      \begin{center} 
-      $(\delta(q, c), \delta(p,c))$ 
-      \end{center} 
-      
-      are marked. If there is one, then also mark $(q, p)$.
-\item Repeat last step until no change.
-\item All unmarked pairs can be merged.
-\end{enumerate}
-
-\noindent To illustrate this algorithm, consider the following 
-DFA.
-
-\begin{center}
-\begin{tikzpicture}[>=stealth',very thick,auto,
-                    every state/.style={minimum size=0pt,
-                    inner sep=2pt,draw=blue!50,very thick,
-                    fill=blue!20}]
-\node[state,initial]  (Q_0)  {$Q_0$};
-\node[state] (Q_1) [right=of Q_0] {$Q_1$};
-\node[state] (Q_2) [below right=of Q_0] {$Q_2$};
-\node[state] (Q_3) [right=of Q_2] {$Q_3$};
-\node[state, accepting] (Q_4) [right=of Q_1] {$Q_4$};
-\path[->] (Q_0) edge node [above]  {$a$} (Q_1);
-\path[->] (Q_1) edge node [above]  {$a$} (Q_4);
-\path[->] (Q_4) edge [loop right] node  {$a, b$} ();
-\path[->] (Q_3) edge node [right]  {$a$} (Q_4);
-\path[->] (Q_2) edge node [above]  {$a$} (Q_3);
-\path[->] (Q_1) edge node [right]  {$b$} (Q_2);
-\path[->] (Q_0) edge node [above]  {$b$} (Q_2);
-\path[->] (Q_2) edge [loop left] node  {$b$} ();
-\path[->] (Q_3) edge [bend left=95, looseness=1.3] node 
-  [below]  {$b$} (Q_0);
-\end{tikzpicture}
-\end{center}
-
-\noindent In Step 1 and 2 we consider essentially a triangle
-of the form
-
-\begin{center}
-\begin{tikzpicture}[scale=0.6,line width=0.8mm]
-\draw (0,0) -- (4,0);
-\draw (0,1) -- (4,1);
-\draw (0,2) -- (3,2);
-\draw (0,3) -- (2,3);
-\draw (0,4) -- (1,4);
-
-\draw (0,0) -- (0, 4);
-\draw (1,0) -- (1, 4);
-\draw (2,0) -- (2, 3);
-\draw (3,0) -- (3, 2);
-\draw (4,0) -- (4, 1);
-
-\draw (0.5,-0.5) node {$Q_0$}; 
-\draw (1.5,-0.5) node {$Q_1$}; 
-\draw (2.5,-0.5) node {$Q_2$}; 
-\draw (3.5,-0.5) node {$Q_3$};
- 
-\draw (-0.5, 3.5) node {$Q_1$}; 
-\draw (-0.5, 2.5) node {$Q_2$}; 
-\draw (-0.5, 1.5) node {$Q_3$}; 
-\draw (-0.5, 0.5) node {$Q_4$}; 
-
-\draw (0.5,0.5) node {\large$\star$}; 
-\draw (1.5,0.5) node {\large$\star$}; 
-\draw (2.5,0.5) node {\large$\star$}; 
-\draw (3.5,0.5) node {\large$\star$};
-\end{tikzpicture}
-\end{center}
-
-\noindent where the lower row is filled with stars, because in
-the corresponding pairs there is always one state that is
-accepting ($Q_4$) and a state that is non-accepting (the other
-states).
-
-Now in Step 3 we need to fill in more stars according whether 
-one of the next-state pairs are marked. We have to do this 
-for every unmarked field until there is no change anymore.
-This gives the triangle
-
-\begin{center}
-\begin{tikzpicture}[scale=0.6,line width=0.8mm]
-\draw (0,0) -- (4,0);
-\draw (0,1) -- (4,1);
-\draw (0,2) -- (3,2);
-\draw (0,3) -- (2,3);
-\draw (0,4) -- (1,4);
-
-\draw (0,0) -- (0, 4);
-\draw (1,0) -- (1, 4);
-\draw (2,0) -- (2, 3);
-\draw (3,0) -- (3, 2);
-\draw (4,0) -- (4, 1);
-
-\draw (0.5,-0.5) node {$Q_0$}; 
-\draw (1.5,-0.5) node {$Q_1$}; 
-\draw (2.5,-0.5) node {$Q_2$}; 
-\draw (3.5,-0.5) node {$Q_3$};
- 
-\draw (-0.5, 3.5) node {$Q_1$}; 
-\draw (-0.5, 2.5) node {$Q_2$}; 
-\draw (-0.5, 1.5) node {$Q_3$}; 
-\draw (-0.5, 0.5) node {$Q_4$}; 
-
-\draw (0.5,0.5) node {\large$\star$}; 
-\draw (1.5,0.5) node {\large$\star$}; 
-\draw (2.5,0.5) node {\large$\star$}; 
-\draw (3.5,0.5) node {\large$\star$};
-\draw (0.5,1.5) node {\large$\star$}; 
-\draw (2.5,1.5) node {\large$\star$}; 
-\draw (0.5,3.5) node {\large$\star$}; 
-\draw (1.5,2.5) node {\large$\star$}; 
-\end{tikzpicture}
-\end{center}
-
-\noindent which means states $Q_0$ and $Q_2$, as well as $Q_1$
-and $Q_3$ can be merged. This gives the following minimal DFA
-
-\begin{center}
-\begin{tikzpicture}[>=stealth',very thick,auto,
-                    every state/.style={minimum size=0pt,
-                    inner sep=2pt,draw=blue!50,very thick,
-                    fill=blue!20}]
-\node[state,initial]  (Q_02)  {$Q_{0, 2}$};
-\node[state] (Q_13) [right=of Q_02] {$Q_{1, 3}$};
-\node[state, accepting] (Q_4) [right=of Q_13] 
-  {$Q_{4\phantom{,0}}$};
-\path[->] (Q_02) edge [bend left] node [above]  {$a$} (Q_13);
-\path[->] (Q_13) edge [bend left] node [below]  {$b$} (Q_02);
-\path[->] (Q_02) edge [loop below] node  {$b$} ();
-\path[->] (Q_13) edge node [above]  {$a$} (Q_4);
-\path[->] (Q_4) edge [loop above] node  {$a, b$} ();
-\end{tikzpicture}
-\end{center}
-
-\subsubsection*{Regular Languages}
+\subsection*{Regular Languages}
 
 Given the constructions in the previous sections we obtain 
 the following overall picture:
@@ -1381,7 +1390,7 @@
 derivatives or NFAs or DFAs. But let us quickly look at what
 the differences mean in computational terms. Translating a
 regular expression into a NFA gives us an automaton that has
-$O(n)$ nodes---that means the size of the NFA grows linearly
+$O(n)$ states---that means the size of the NFA grows linearly
 with the size of the regular expression. The problem with NFAs
 is that the problem of deciding whether a string is accepted
 or not is computationally not cheap. Remember with NFAs we
@@ -1441,11 +1450,11 @@
 automaton for this language, but again that would lead us too
 far afield for what we want to do in this module.
 
-\section*{Further Reading}
+%\section*{Further Reading}
 
-Compare what a ``human expert'' would create as an automaton for the
-regular expression $a (b + c)^*$ and what the Thomson
-algorithm generates.
+%Compare what a ``human expert'' would create as an automaton for the
+%regular expression $a\cdot (b + c)^*$ and what the Thomson
+%algorithm generates.
 
 %http://www.inf.ed.ac.uk/teaching/courses/ct/
 \end{document}




