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

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

\noindent 

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

\begin{itemize}

\item $\delta$ is the transition function.

\end{itemize}

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

\end{tikzpicture}

\end{center}

\[

\begin{array}{lcl}

\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

\[

\]

\noindent I let you think about a definition that describes

the set of strings accepted by an automaton. 

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

                  {../progs/dfa.scala}

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

  construction by lifting the transition (partial) function to

  lists of \texttt{C}haracters. Since \texttt{delta} is given

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

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

\end{figure}

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

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?

\begin{itemize}

\item $\rho$ is a transition relation.

\end{itemize}

\noindent

\begin{center}

\end{center}

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

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

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

\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, 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 (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]  (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 [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 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.

\subsubsection*{Subset Construction}

What is interesting is that for every NFA we can find a DFA

which recognises the same language. This can, for example, be

done by the \emph{subset construction}. Consider again the NFA

below on the left, consisting of nodes labeled $0$, $1$ and $2$. 

\begin{center}