\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../graphics}

%We can even allow ``silent

%transitions'', also called epsilon-transitions. They allow us

%to go from one state to the next without having a character

%consumed. We label such silent transition with the letter

%$\epsilon$.

\begin{document}

\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}

\section*{Handout 3 (Finite Automata)}

Every formal language and compiler course I know of bombards you first

with automata and then to a much, much smaller extend with regular

expressions. As you can see, this course is turned upside down:

regular expressions come first. The reason is that regular expressions

are easier to reason about and the notion of derivatives, although

already quite old, only became more widely known rather

recently. Still let us in this lecture have a closer look at automata

and their relation to regular expressions. This will help us with

understanding why the regular expression matchers in Python, Ruby and

Java are so slow with certain regular expressions.

\subsection*{Deterministic Finite Automata}

The central definition is:\medskip

\noindent 

A \emph{deterministic finite automaton} (DFA), say $A$, is

\begin{itemize}

\item $Qs$ is a finite set of states,

\item $Q_0 \in Qs$ is the start state,

\item $F \subseteq Qs$ 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 transition 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 ``failure

exception''.  That means actually we have \emph{partial} functions as

\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},scale=2]

\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 this graphical notation, the accepting state $Q_4$ is

indicated with double circles. Note that there can be more than one

accepting state. It is also 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 also 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}

\]

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}

\end{array}

\]

\noindent This lifted transition function is often called

``delta-hat''. Given a string, we start in the starting state and 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 by the

automaton. Otherwise it is not accepted. This also means that if along

the way we hit the case where the transition function $\delta$ is not

defined, we need to raise an error. In our implementation we will deal

with this case elegantly by using Scala's \texttt{Try}. So a string

\[

\]

\noindent I let you think about a definition that describes

the set of all strings accepted by an automaton. 

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]

                  {../progs/dfa.scala}

\caption{A Scala implementation of DFAs using partial functions.

  Notice some subtleties: \texttt{deltas} implements the delta-hat

  construction by lifting the transition (partial) function to

  lists of characters. Since \texttt{delta} is given

  as a partial function, it can obviously go ``wrong'' in which

  case the \texttt{Try} in \texttt{accepts} catches the error and

  returns \texttt{false}---that means the string is not accepted.

  The example \texttt{delta} implements the DFA example shown

  earlier in the handout.\label{dfa}}

\end{figure}

Figure~\ref{dfa}. As you can see, there are many features of the

mathematical definition that are quite closely reflected in the

code. In the DFA-class, there is a starting state, called

\texttt{start}, with the polymorphic type \texttt{A}.  There is a

partial function \texttt{delta} for specifying the transitions---these

partial functions take a state (of polymorphic type \texttt{A}) and an

input (of polymorphic type \texttt{C}) and produce a new state (of

type \texttt{A}). For the moment it is OK to assume that \texttt{A} is

some arbitrary type for states and the input is just characters.  (The

DFAs will become clearer later on.)

{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=

                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]

abstract class State

...

case object Sink extends State

val delta : (State, Char) :=> State = 

  { case (S0, 'a') => S1

    case (S1, 'a') => S2

    case _ => Sink

  }

\end{lstlisting}}  

I let you ponder whether this is a good implementation of DFAs. In

\subsection*{Non-Deterministic Finite Automata}

character what the next state is (potentially none), it will be useful

potential successor states. We even allow more than one starting

\begin{itemize}

\item $Qs$ is a finite set of states

\item $Q_{0s}$ is a set of start states ($Q_{0s} \subseteq Qs$)

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

\item $\rho$ is a transition relation.

\end{itemize}

\noindent

A typical example of a NFA is

% A NFA for (ab* + b)*a

\begin{center}

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

    every state/.style={minimum size=0pt,inner sep=3pt,

      draw=blue!50,very thick,fill=blue!20},scale=2]

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

\node[state] (Q_1) [right=of Q_0] {$Q_1$};

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

\path[->] (Q_0) edge [loop above] node  {$b$} ();

\path[<-] (Q_0) edge node [below]  {$b$} (Q_1);

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

\path[->] (Q_0) edge [bend right] node [below]  {$a$} (Q_2);

\path[->] (Q_1) edge [loop above] node  {$a,b$} ();

\path[->] (Q_1) edge node  [above] {$a$} (Q_2);

\end{tikzpicture}

\end{center}

\noindent

This NFA happens to have only one starting state, but in general there

could be more.  Notice that in state $Q_0$ we might go to state $Q_1$

\emph{or} to state $Q_2$ when receiving an $a$. Similarly in state

There are a number of additional points you should note with

NFAs. 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 again at the NFA above: if you are currently in

the state $Q_1$ and you read a character $b$, then you can transition

to either $Q_0$ \emph{or} $Q_2$. Which route, or output, you take is

not determined.  This non-determinism can be represented by a

relation.

My implementation of NFAs in Scala is shown in Figure~\ref{nfa}.

Perhaps interestingly, I do not actually use relations for my NFAs,

and I also do not use transition functions that return sets of states

(another popular choice for implementing NFAs).  For reasons that

become clear in a moment, I use sets of partial functions

instead---see Line 7 in Figure~\ref{nfa}. DFAs have only one such

partial function; my NFAs have a set.  Another parameter,

function from states to booleans. The \texttt{next} function

calculates the set of next states reachable from a single state

through all the partial functions in the \texttt{delta}-set and apply

\texttt{Some}s (in case the application succeeded) and possibly some

\texttt{None}s (in case the partial function is not defined or produces an

error).  The \texttt{None}s are filtered out by the \texttt{flatMap},

leaving the values inside the \texttt{Some}s. The function

\texttt{nexts} just lifts this function to sets of

states. \texttt{Deltas} and \texttt{accept} are similar to the DFA

definitions.

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]

                  {../progs/nfa.scala}

\caption{A Scala implementation of NFAs using sets of partial functions.

  Notice some subtleties: Since \texttt{delta} is given

  as a set of partial functions, each of them can obviously go ``wrong'' in which

  case the \texttt{Try}. The function \texttt{accepts} implements the

  acceptance of a string in a breath-first fashion. This can be costly

  way of deciding whether a string is accepted in practical contexts.\label{nfa}}

\end{figure}

The reason for using sets of partial functions for specifying the

\begin{center}

\begin{tikzpicture}[>=stealth',very thick, auto, node distance=7mm,

    every state/.style={minimum size=0pt,inner sep=1pt,

      draw=blue!50,very thick,fill=blue!20},scale=0.5]

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

\node[state] (Q_1) [right=of Q_0] {$Q_1$};

\node[state] (Q_2) [right=of Q_1] {$Q_2$};

\node[state] (Q_3) [right=of Q_2] {$Q_3$};

\node[state] (Q_4) [right=of Q_3] {$Q_4$};

\node[state] (Q_5) [right=of Q_4] {$Q_5$};

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

\path[->] (Q_0) edge [loop above] node  {$.$} ();

\path[->] (Q_0) edge node [above]  {$a$} (Q_1);

\path[->] (Q_1) edge node [above]  {$.$} (Q_2);

\path[->] (Q_2) edge node [above]  {$.$} (Q_3);

\path[->] (Q_3) edge node [above]  {$.$} (Q_4);

\path[->] (Q_4) edge node [above]  {$b$} (Q_5);

\path[->] (Q_5) edge node [above]  {$c$} (Q_6);

\end{tikzpicture}

\end{center}

\noindent

are in $Q_0$ and read an $a$ we can either stay in $Q_0$ (since any

character will do for this) or advance to $Q_1$ (but only if it is an

$a$). Why this is a good benchmark regular expression is irrelevant

here. The point is that this NFA can be conveniently represented by

the code:

{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=

                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]

val delta = Set[(State, Char) :=> State](

  { case (Q0, 'a') => Q1 },

  { case (Q0, _)   => Q0 },

  { case (Q1, _)   => Q2 },

  { case (Q2, _)   => Q3 },

  { case (Q3, _)   => Q4 },

  { case (Q4, 'b') => Q5 },

  { case (Q5, 'c') => Q6 }

)

NFA(Set[State](Q0), delta, Set[State](Q6))

\end{lstlisting}}

\noindent

where the $.$-transitions translate into a

underscore-pattern-matching. Recall that in $Q_0$ if we read an $a$ we

can go to $Q_1$ (by the first partial function in the set) and also

stay in $Q_0$ (by the second partial function). Representing such

Look very careful again at the \texttt{accepts} and \texttt{deltas}

functions in NFAs and remember that when accepting a string by an NFA

{\small\begin{lstlisting}[language=Scala,linebackgroundcolor=

                  {\ifodd\value{lstnumber}\color{capri!3}\fi}]

def search(q: A, s: List[C]) : Boolean = s match {

  case Nil => fins(q)

  case c::cs =>

}

def accepts(s: List[C]) : Boolean = 

  starts.exists(search(_, s))

\end{lstlisting}}

\noindent

This depth-first way of exploration seems to work efficiently in many

examples and is much less of strain on memory. The problem is that the

catastrophic backtracking from earlier lectures. This depth-first

search with backtracking is the reason for the abysmal performance of

%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 the special silent

%transition in NFAs. As mentioned already this transition means you do

%not have to ``consume'' any part of the input string, but ``silently''

%change to a different state. In the left picture, for example, if you

%are in the starting state, you can silently move either to $Q_1$ or

%%$Q_2$. This silent transition is also often called

%\emph{$\epsilon$-transition}.

\subsubsection*{Thompson Construction}

The reason for introducing NFAs is that there is a relatively

simple (recursive) translation of regular expressions into

NFAs. Consider the simple regular expressions $\ZERO$,

$\ONE$ and $c$. They can be translated as follows:

\begin{center}

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

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

\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}{$\ONE$} & 

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