diff -r 83e6cb90216d -r 4dbeaf43031d handouts/ho03.tex
--- a/handouts/ho03.tex	Sat Oct 11 13:09:15 2014 +0100
+++ b/handouts/ho03.tex	Sat Oct 11 13:50:36 2014 +0100
@@ -464,6 +464,151 @@
 
 \subsubsection*{Automata Minimization}
 
+As seen in the subset construction, the translation 
+of an 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}
 
 Given the constructions in the previous sections we obtain 
@@ -549,6 +694,9 @@
 the accepting and non-accepting states. You can then translate
 this DFA back into a regular expression. 
 
+Not all languages are regular\ldots{}
+
+
 \end{document}
 
 %%% Local Variables: