--- a/handouts/ho03.tex	Sat Oct 12 10:13:52 2013 +0100
+++ b/handouts/ho03.tex	Sat Oct 12 23:39:20 2013 +0100
@@ -6,6 +6,15 @@
 \usepackage[T1]{fontenc}
 \usepackage{listings}
 \usepackage{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{shapes}
+\usetikzlibrary{shadows}
+\usetikzlibrary{positioning}
+\usetikzlibrary{calc}
+\usetikzlibrary{fit}
+\usetikzlibrary{backgrounds}
 
 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
 
@@ -49,6 +58,40 @@
 
 \section*{Handout 3}
 
+Let us have a closer look at automata and their relation to regular expressions. This will help us to understand
+why the regular expression matchers in Python and Ruby are so slow with certain regular expressions. 
+
+A deterministic finite automaton (DFA), say $A$, is defined by  a four-tuple $A(Q, q_0, F, \delta)$ where
+
+\begin{itemize}
+\item $Q$ is a set of states,
+\item $q_0 \in Q$ is the start state,
+\item $F \subseteq Q$ are the accepting states, and
+\item $\delta$ is the transition function.
+\end{itemize}
+
+\noindent
+The transition function determines 
+A typical example of a DFA is
+
+\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}
 
 \end{document}