\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../graphics}

\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. On the way we will

also see what are the limitations of regular

expressions. Unfortunately, they cannot be used for \emph{everything}.

\subsection*{Deterministic Finite Automata}

Lets start\ldots the central definition is:\medskip

\noindent 

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

given by a five-tuple written ${\cal A}(\varSigma, Qs, Q_0, F, \delta)$ where

\begin{itemize}

\item $\varSigma$ is an alphabet,  

\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 I am sure you have seen this defininition already

before. 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

transitions---see the Scala implementation of DFAs later on.  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},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

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

\widehat{\delta}(q, [])        & \dn & q\\

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

\end{array}

\]

\noindent This lifted transition function is often called

\emph{delta-hat}. Given a string, we start in the starting state and

take the first character of the string, follow to the next state, 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 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}.  Summing up: a

string $s$ is in the \emph{language accepted by the automaton} ${\cal

  A}(\varSigma, Q, Q_0, F, \delta)$ iff

\[

\widehat{\delta}(Q_0, s) \in F 

\]

\noindent I let you think about a definition that describes the set of

all strings accepted by a determinsitic finite automaton.

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

                  {../progs/display/dfa.scala}

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

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

  construction by lifting the (partial) transition  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} in

  Line 28--38 implements the DFA example shown earlier in the

  handout.\label{dfa}}

\end{figure}

My take on an implementation of DFAs in Scala is given in

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

reason for not having concrete types, but polymorphic types for the

states and the input of DFAs will become clearer later on.)

The DFA-class has also an argument for specifying final states. In the

implementation it is not a set of states, as in the mathematical

definition, but a function from states to booleans (this function is

supposed to return true whenever a state is final; false

otherwise). While this boolean function is different from the sets of

states, Scala allows to use sets for such functions (see Line 40 where

the DFA is initialised). Again it will become clear later on why I use

functions for final states, rather than sets.

The most important point in the implementation is that I use Scala's

partial functions for representing the transitions; alternatives would

have been \texttt{Maps} or even \texttt{Lists}. One of the main

advantages of using partial functions is that transitions can be quite

nicely defined by a series of \texttt{case} statements (see Lines 28

-- 38 for an example). If you need to represent an automaton with a

sink state (catch-all-state), you can use Scala's pattern matching and

write something like

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

\noindent I let you think what the corresponding DFA looks like in the

graph notation.

Finally, I let you ponder whether this is a good implementation of

DFAs or not. In doing so I hope you notice that the $\varSigma$ and

$Qs$ components (the alphabet and the set of finite states,

respectively) are missing from the class definition. This means that

the implementation allows you to do some fishy things you are not

meant to do with DFAs. Which fishy things could that be?

\subsection*{Non-Deterministic Finite Automata}

Remember we want to find out what the relation is between regular

expressions and automata. To do this with DFAs is a bit unwieldy.

While with DFAs it is always clear that given a state and a character

what the next state is (potentially none), it will be convenient to

relax this restriction. That means we allow states to have several

potential successor states. We even allow more than one starting

state. The resulting construction is called a \emph{Non-Deterministic

  Finite Automaton} (NFA) given also as a five-tuple ${\cal

  A}(\varSigma, Qs, Q_{0s}, F, \rho)$ where

\begin{itemize}

\item $\varSigma$ is an alphabet,  

\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

$Q_1$ and receiving an $a$, we can stay in state $Q_1$ \emph{or} go to

$Q_2$. This kind of choice is not allowed with DFAs. The downside of

this choice in NFAs is that when it comes to deciding whether a string is

accepted by a NFA we potentially have to explore all possibilities. I

let you think which strings the above NFA accepts.

There are a number of additional points you should note about

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,

but use transition functions that return sets of states.  DFAs have

partial transition functions that return a single state; my NFAs

return a set of states. I let you think about this representation for

NFA-transitions and how it corresponds to the relations used in the

mathematical definition of NFAs. An example of a transition function

in Scala for the NFA shown above is

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

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

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

  { case (Q0, 'a') => Set(Q1, Q2)

    case (Q0, 'b') => Set(Q0)

    case (Q1, 'a') => Set(Q1, Q2)

    case (Q1, 'b') => Set(Q0, Q1) }

\end{lstlisting}}  

\noindent Like in the mathematical definition, \texttt{starts} is in

NFAs a set of states; \texttt{fins} is again a function from states to

booleans. The \texttt{next} function calculates the set of next states

reachable from a single state \texttt{q} by a character~\texttt{c}. In

case there is no such state---the partial transition function is

undefined---the empty set is returned (see function

\texttt{applyOrElse} in Lines 9 and 10). The function \texttt{nexts}

just lifts this function to sets of states.

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

                  {../progs/display/nfa.scala}

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

  Notice that the function \texttt{accepts} implements the

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

  way of deciding whether a string is accepted or not in applications that need to handle

  large NFAs and large inputs.\label{nfa}}

\end{figure}

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

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

we might have to explore all possible transitions (recall which state

to go to is not unique anymore with NFAs\ldots{}we need to explore

potentially all next states). The implementation achieves this

exploration through a \emph{breadth-first search}. This is fine for

small NFAs, but can lead to real memory problems when the NFAs are

bigger and larger strings need to be processed. As result, some

regular expression matching engines resort to a \emph{depth-first

  search} with \emph{backtracking} in unsuccessful cases. In our

implementation we can implement a depth-first version of

\texttt{accepts} using Scala's \texttt{exists}-function as follows:

{\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 => next(q, c).exists(search(_, cs)) 

}

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

  starts.exists(search(_, s))

\end{lstlisting}}

\noindent

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

many examples and is much less of a strain on memory. The problem is

that the backtracking can get ``catastrophic'' in some

examples---remember the catastrophic backtracking from earlier

lectures. This depth-first search with backtracking is the reason for

the abysmal performance of some regular expression matchings in Java,

Ruby and Python. I like to show you this in the next two sections.

\subsubsection*{Epsilon NFAs}

In order to get an idea what calculations are performed by Java \&

friends, we need a method for transforming a regular expression into

an automaton. This automaton should accept exactly those strings that

are accepted by the regular expression.  The simplest and most

well-known method for this is called \emph{Thompson Construction},

after the Turing Award winner Ken Thompson. This method is by

recursion over regular expressions and depends on the non-determinism

in NFAs described in the previous section. You will see shortly why

this construction works well with NFAs, but is not so straightforward

with DFAs.

Unfortunately we are still one step away from our intended target

though---because this construction uses a version of NFAs that allows

``silent transitions''. The idea behind silent transitions is that

they allow us to go from one state to the next without having to

consume a character. We label such silent transition with the letter

$\epsilon$ and call the automata $\epsilon$NFAs. Two typical examples

of $\epsilon$NFAs are:

\begin{center}

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

\begin{tikzpicture}[>=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 right] node  {$a$} ();

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

\end{tikzpicture} &

\raisebox{20mm}{

\begin{tikzpicture}[>=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

Consider the $\epsilon$NFA on the left-hand side: the

$\epsilon$-transitions mean you do not have to ``consume'' any part of

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

this example, if you are in the starting state $Q_0$, you can silently

move either to $Q_1$ or $Q_2$. You can see that once you are in $Q_1$,

respectively $Q_2$, you cannot ``go back'' to the other states. So it

seems allowing $\epsilon$-transitions is a rather substancial

extension to NFAs. On first appearances, $\epsilon$-transitions might

even look rather strange, or even silly. To start with, silent

transitions make the decision whether a string is accepted by an

automaton even harder: with $\epsilon$NFAs we have to look whether we

can do first some $\epsilon$-transitions and then do a

``proper''-transition; and after any ``proper''-transition we again

have to check whether we can do again some silent transitions. Even

worse, if there is a silent transition pointing back to the same

state, then we have to be careful our decision procedure for strings

does not loop (remember the depth-first search for exploring all

states).

The obvious question is: Do we get anything in return for this hassle

with silent transitions?  Well, we still have to work for it\ldots

unfortunately.  If we were to follow the many textbooks on the

subject, we would now start with defining what $\epsilon$NFAs

are---that would require extending the transition relation of

NFAs. Next, we woudl show that the $\epsilon$NFAs are equivalent to

NFAs and so on. Once we have done all this on paper, we would need to

implement $\epsilon$NFAs. Lets try to take a shortcut instead. We are

not really interested in $\epsilon$NFAs; they are only a convenient

tool for translating regular expressions into automata. So we are not

going to implementing them explicitly, but translate them immediately

into NFAs (in a sense $\epsilon$NFAs are just a convenient API for

lazy people ;o).  How does the translation work? Well we have to find

all transitions of the form

\[

q\stackrel{\epsilon}{\longrightarrow}\ldots\stackrel{\epsilon}{\longrightarrow}

\;\stackrel{a}{\longrightarrow}\;

\stackrel{\epsilon}{\longrightarrow}\ldots\stackrel{\epsilon}{\longrightarrow} q'

\]

\noindent and replace them with $q \stackrel{a}{\longrightarrow}

q'$. Doing this to the $\epsilon$NFA on the right-hand side above gives

the NFA

\begin{center}

\begin{tikzpicture}[>=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 [above]  {$b$} (r_3);

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

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

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

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

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

\end{tikzpicture}

\end{center}

\noindent where the single $\epsilon$-transition is replaced by

three additional $a$-transitions. Please do the calculations yourself

and verify that I did not forget any transition.

So in what follows, whenever we are given an $\epsilon$NFA we will

replace it by an equivalent NFA. The Scala code for this translation

is given in Figure~\ref{enfa}. The main workhorse in this code is a

function that calculates a fixpoint of function (Lines 5--10). This

function is used for ``discovering'' which states are reachable by

$\epsilon$-transitions. Once no new state is discovered, a fixpoint is

reached. This is used for example when calculating the starting states

of an equivalent NFA (see Line 36): we start with all starting states

of the $\epsilon$NFA and then look for all additional states that can

be reached by $\epsilon$-transitions. We keep on doing this until no

new state can be reached. This is what the $\epsilon$-closure, named

in the code \texttt{ecl}, calculates. Similarly, an accepting state of

the NFA is when we can reach an accepting state of the $\epsilon$NFA

by $\epsilon$-transitions.

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

                  {../progs/display/enfa.scala}

\caption{A Scala function that translates $\epsilon$NFA into NFAs. The

  transtion function of $\epsilon$NFA takes as input an \texttt{Option[C]}.

  \texttt{None} stands for an $\epsilon$-transition; \texttt{Some(c)}

  for a ``proper'' transition consuming a character. The functions in

  Lines 18--26 calculate

  all states reachable by one or more $\epsilon$-transition for a given

  set of states. The NFA is constructed in Lines 36--38.\label{enfa}}

\end{figure}

Also look carefully how the transitions of $\epsilon$NFAs are

implemented. The additional possibility of performing silent

transitions is encoded by using \texttt{Option[C]} as the type for the

``input''. The \texttt{Some}s stand for ``propper'' transitions where

a character is consumed; \texttt{None} stands for

$\epsilon$-transitions. The transition functions for the two

$\epsilon$NFAs from the beginning of this section can be defined as