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

\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

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

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}

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

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

\end{array}

\]

\noindent This lifted transition function is often called

``delta-hat''. Given a string, 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 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

\delta)$ iff

\[

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

\]

\noindent I let you think about a definition that describes

\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

  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}

A simple Scala implementation for DFAs is given in

mathematical definition that are quite closely reflected in the

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

{\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 The DFA-class has also an argument for specifying final

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

doing so I hope you notice that the $Qs$ component (the set of finite

states) is 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}

While with DFAs it will always be clear that given a state and a

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

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

potential successor states. We even allow more than one starting

state. The resulting construction is called a \emph{non-deterministic

\rho)$ where

\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 NFA for (ab* + b)*a

\begin{center}

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

\begin{figure}[t]

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

\end{figure}

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

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