\documentclass{article}

\usepackage{hyperref}

\usepackage{amssymb}

\usepackage{amsmath}

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

\usepackage{../langs}

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%

\begin{document}

\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 \emph{deterministic finite automaton} (DFA), say $A$, is defined by  a four-tuple written $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 how to ``transition'' from one state to the next state with respect to a character.

We have the assumption that these functions do not need to be defined everywhere: so it can be the case that

given a character there is no next state, in which case we need to raise a kind of ``raise an exception''.  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}

\noindent

The accepting state $q_4$ is indicated with double circles. It is possible that a DFA has no

accepting states at all, or that the starting state is also an accepting state.

In the case above the transition function is defined everywhere and can be given as a table

as follows:

\[

\begin{array}{lcl}

(q_0, a) &\rightarrow& q_1\\

(q_0, b) &\rightarrow& q_2\\

(q_1, a) &\rightarrow& q_4\\

(q_1, b) &\rightarrow& q_2\\

(q_2, a) &\rightarrow& q_3\\

(q_2, b) &\rightarrow& q_2\\

(q_3, a) &\rightarrow& q_4\\

(q_3, b) &\rightarrow& q_0\\

(q_4, a) &\rightarrow& q_4\\

(q_4, b) &\rightarrow& q_4\\

\end{array}

\]

\noindent

We need to define the notion of what language is accepted by an automaton. For this we 

lift the transition function $\delta$ from characters to strings as follows:

\[

\begin{array}{lcl}

\hat{\delta}(q, "")        & \dn & q\\

\hat{\delta}(q, c\!::\!s) & \dn & \hat{\delta}(\delta(q, c), s)\\

\end{array}

\]

\noindent

Given a string this means we start in the starting state and take the first character of the string,

follow to the next sate, then take the second character and so on. Once the string is exhausted

and we end up in an accepting state, then this string is accepted. Otherwise it is not accepted. 

So $s$ in the \emph{language accepted by the automaton} $A(Q, q_0, F, \delta)$ iff

\[

\hat{\delta}(q_0, s) \in F 

\]

While with DFA it will always clear that given a character what the next state is, it will be useful to relax 

this restriction. The resulting construction is called a \emph{non-deterministic finite automaton} (NFA) given

as a four-tuple $A(Q, q_0, F, \rho)$ where

\begin{itemize}

\item $Q$ is a finite set of states

\item $q_0$ is a start state

\item $F$ are some accepting states with $F \subseteq Q$, and

\item $\rho$ is a transition relation.

\end{itemize}

\noindent

Two typical examples of NFAs are

\begin{center}

\begin{tabular}[t]{c@{\hspace{9mm}}c}

\begin{tikzpicture}[scale=0.7,>=stealth',very thick,

                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

\node[state,initial]  (q_0)  {$q_0$};

\node[state] (q_1) [above=of q_0] {$q_1$};

\node[state, accepting] (q_2) [below=of q_0] {$q_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$} ();

\end{tikzpicture} &

\raisebox{20mm}{

\begin{tikzpicture}[scale=0.7,>=stealth',very thick,

                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

\node[state,initial]  (r_1)  {$r_1$};

\node[state] (r_2) [above=of r_1] {$r_2$};

\node[state, accepting] (r_3) [right=of r_1] {$r_3$};

\path[->] (r_1) edge node [below]  {$b$} (r_3);

\path[->] (r_2) edge [bend left] node [above]  {$a$} (r_3);

\path[->] (r_1) edge [bend left] node  [left] {$\epsilon$} (r_2);

\path[->] (r_2) edge [bend left] node  [right] {$a$} (r_1);

\end{tikzpicture}}

\end{tabular}

\end{center}

\noindent

There are a number of points you should note. Every DFA is a NFA, but not vice versa.

The $\rho$ in NFAs is a transition \emph{relation} 

(DFAs have a transition function). The difference between a function and a relation is that a function 

has always a single output, while a relation gives, roughly speaking, several outputs. Look

at the NFA on the right-hand side above: if you are currently in the state $r_2$ and you read a

character $a$, then you can transition to $r_1$ \emph{or} $r_3$. Which route you take is not

determined. This means if we need to decide whether a string is accepted by a NFA, we might have 

to explore all possibilities. Also there is a special transition in NFAs which is called \emph{epsilon-transition}

or \emph{silent transition}. This transition means you do not have to ``consume'' no part of

the input string, but ``silently'' change to a different state.

The reason for introducing NFAs is that there is a relatively simple (recursive) translation of regular expressions into

NFAs. Consider the simple regular expressions $\varnothing$, $\epsilon$ and $c$. They can be translated

as follows:

\begin{center}

\begin{tabular}[t]{l@{\hspace{10mm}}l}

\raisebox{1mm}{$\varnothing$} & 

\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial]  (q_0)  {$\mbox{}$};

\end{tikzpicture}\\\\

\raisebox{1mm}{$\epsilon$} & 

\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial, accepting]  (q_0)  {$\mbox{}$};

\end{tikzpicture}\\\\

\raisebox{2mm}{$c$} & 

\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial]  (q_0)  {$\mbox{}$};

\node[state, accepting]  (q_1)  [right=of q_0] {$\mbox{}$};

\path[->] (q_0) edge node [below]  {$c$} (q_1);

\end{tikzpicture}\\\\

\end{tabular}

\end{center}

\noindent

The case for the sequence regular expression $r_1 \cdot r_2$ is as follows: We are given by recursion

two automata representing $r_1$ and $r_2$ respectively. 

\begin{center}

\begin{tikzpicture}[node distance=3mm,

                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial]  (q_0)  {$\mbox{}$};

\node (r_1)  [right=of q_0] {$\ldots$};

\node[state, accepting]  (t_1)  [right=of r_1] {$\mbox{}$};

\node[state, accepting]  (t_2)  [above=of t_1] {$\mbox{}$};

\node[state, accepting]  (t_3)  [below=of t_1] {$\mbox{}$};

\node[state, initial]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};

\node (b_1)  [right=of a_0] {$\ldots$};

\node[state, accepting]  (c_1)  [right=of b_1] {$\mbox{}$};

\node[state, accepting]  (c_2)  [above=of c_1] {$\mbox{}$};

\node[state, accepting]  (c_3)  [below=of c_1] {$\mbox{}$};

\begin{pgfonlayer}{background}

\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};

\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};

\node [yshift=2mm] at (1.north) {$r_1$};

\node [yshift=2mm] at (2.north) {$r_2$};

\end{pgfonlayer}

\end{tikzpicture}

\end{center}

\noindent

The first automaton has some accepting states. We obtain an automaton for $r_1\cdot r_2$ by connecting

these accepting states with $\epsilon$-transitions to the starting state of the second automaton. By doing 

so we make them non-accepting like so:

\begin{center}

\begin{tikzpicture}[node distance=3mm,

                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node[state, initial]  (q_0)  {$\mbox{}$};

\node (r_1)  [right=of q_0] {$\ldots$};

\node[state]  (t_1)  [right=of r_1] {$\mbox{}$};

\node[state]  (t_2)  [above=of t_1] {$\mbox{}$};

\node[state]  (t_3)  [below=of t_1] {$\mbox{}$};

\node[state]  (a_0)  [right=2.5cm of t_1] {$\mbox{}$};

\node (b_1)  [right=of a_0] {$\ldots$};

\node[state, accepting]  (c_1)  [right=of b_1] {$\mbox{}$};

\node[state, accepting]  (c_2)  [above=of c_1] {$\mbox{}$};

\node[state, accepting]  (c_3)  [below=of c_1] {$\mbox{}$};

\path[->] (t_1) edge node [above, pos=0.3]  {$\epsilon$} (a_0);

\path[->] (t_2) edge node [above]  {$\epsilon$} (a_0);

\path[->] (t_3) edge node [below]  {$\epsilon$} (a_0);

\begin{pgfonlayer}{background}

\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};

\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};

\end{pgfonlayer}

\end{tikzpicture}

\end{center}

\noindent

The case for the choice regular expression $r_1 + r_2$ is slightly different: We are given by recursion

two automata representing $r_1$ and $r_2$ respectively. 

\begin{center}

\begin{tikzpicture}[node distance=3mm,

                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node at (0,0)  (1)  {$\mbox{}$};

\node[state, initial]  (2)  [above right=16mm of 1] {$\mbox{}$};

\node[state, initial]  (3)  [below right=16mm of 1] {$\mbox{}$};

\node (a)  [right=of 2] {$\ldots$};

\node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};

\node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};

\node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};

\node (b)  [right=of 3] {$\ldots$};

\node[state, accepting]  (b1)  [right=of b] {$\mbox{}$};

\node[state, accepting]  (b2)  [above=of b1] {$\mbox{}$};

\node[state, accepting]  (b3)  [below=of b1] {$\mbox{}$};

\begin{pgfonlayer}{background}

\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};

\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};

\node [yshift=3mm] at (1.north) {$r_1$};

\node [yshift=3mm] at (2.north) {$r_2$};

\end{pgfonlayer}

\end{tikzpicture}

\end{center}

\noindent

Each automaton has a single start state and potentially several accepting states. We obtain a

NFA for the regular expression $r_1 + r_2$ by introducing a new starting state and connecting it

with an $\epsilon$-transition to the two starting states above, like so

\begin{center}

\hspace{2cm}\begin{tikzpicture}[node distance=3mm,

                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node at (0,0) [state, initial]  (1)  {$\mbox{}$};

\node[state]  (2)  [above right=16mm of 1] {$\mbox{}$};

\node[state]  (3)  [below right=16mm of 1] {$\mbox{}$};

\node (a)  [right=of 2] {$\ldots$};

\node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};

\node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};

\node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};

\node (b)  [right=of 3] {$\ldots$};

\node[state, accepting]  (b1)  [right=of b] {$\mbox{}$};

\node[state, accepting]  (b2)  [above=of b1] {$\mbox{}$};

\node[state, accepting]  (b3)  [below=of b1] {$\mbox{}$};

\path[->] (1) edge node [above]  {$\epsilon$} (2);

\path[->] (1) edge node [below]  {$\epsilon$} (3);

\begin{pgfonlayer}{background}

\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};

\node [yshift=3mm] at (3.north) {$r_1+ r_2$};

\end{pgfonlayer}

\end{tikzpicture}

\end{center}

\noindent 

Finally for the $*$-case we have an automaton for $r$

\begin{center}

\begin{tikzpicture}[node distance=3mm,

                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node at (0,0)  (1)  {$\mbox{}$};

\node[state, initial]  (2)  [right=16mm of 1] {$\mbox{}$};

\node (a)  [right=of 2] {$\ldots$};

\node[state, accepting]  (a1)  [right=of a] {$\mbox{}$};

\node[state, accepting]  (a2)  [above=of a1] {$\mbox{}$};

\node[state, accepting]  (a3)  [below=of a1] {$\mbox{}$};

\begin{pgfonlayer}{background}

\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};

\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 also recognise the empty string.

This gives the following automaton for $r^*$:

\begin{center}

\begin{tikzpicture}[node distance=3mm,

                             >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]

\node at (0,0) [state, initial,accepting]  (1)  {$\mbox{}$};

\node[state]  (2)  [right=16mm of 1] {$\mbox{}$};

\node (a)  [right=of 2] {$\ldots$};

\node[state]  (a1)  [right=of a] {$\mbox{}$};

\node[state]  (a2)  [above=of a1] {$\mbox{}$};

\node[state]  (a3)  [below=of a1] {$\mbox{}$};

\path[->] (1) edge node [above]  {$\epsilon$} (2);

\path[->] (a1) edge [bend left=45] node [above]  {$\epsilon$} (1);

\path[->] (a2) edge [bend right] node [below]  {$\epsilon$} (1);

\path[->] (a3) edge [bend left=45] node [below]  {$\epsilon$} (1);

\begin{pgfonlayer}{background}

\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{center}

\noindent

This construction of a NFA from a regular expression was invented by Ken Thompson in 1968.

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: