Binary file handouts/ho03.pdf has changed

--- 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}
 

Binary file slides/slides04.pdf has changed

--- a/slides/slides04.tex	Sat Oct 12 10:13:52 2013 +0100
+++ b/slides/slides04.tex	Sat Oct 12 23:39:20 2013 +0100
@@ -1,6 +1,6 @@
 \documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplainculight}
-\usepackage[T1]{fontenc}
+\usepackage{beamerthemeplaincu}
+%%%\usepackage[T1]{fontenc}
 \usepackage[latin1]{inputenc}
 \usepackage{mathpartir}
 \usepackage[absolute,overlay]{textpos}
@@ -71,7 +71,7 @@
 	showstringspaces=false}
 
 % beamer stuff 
-\renewcommand{\slidecaption}{AFL 04, King's College London, 17.~October 2012}
+\renewcommand{\slidecaption}{AFL 04, King's College London, 16.~October 2013}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 
@@ -91,7 +91,7 @@
   \begin{center}
   \begin{tabular}{ll}
   Email:  & christian.urban at kcl.ac.uk\\
-  Of$\!$fice: & S1.27 (1st floor Strand Building)\\
+  Office: & S1.27 (1st floor Strand Building)\\
   Slides: & KEATS (also home work is there)\\
   \end{tabular}
   \end{center}