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

\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 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 an automaton. 

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

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

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

  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 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 kind of 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. I let you think about this representation for

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

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

\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

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

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

\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

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

interested in $\epsilon$NFAs; they are only a convenient tool for

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}

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}

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

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

  transtions of $\epsilon$NFA take as input an \texttt{Option[C]}.

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

  for a ``proper'' transition. 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 in Lines 36--38.\label{enfa}}

\end{figure}