Java are so slow with certain regular expressions. On the way we will

also see what are the limitations of regular expressions.

Lets start\ldots the central definition is:\medskip

state at all, or that the starting state is also an accepting

\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

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

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

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

  handout.\label{dfa}}

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

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

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

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

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

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

There are a number of additional points you should note about

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

mathematical definition of NFAs.

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.

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

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

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

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

potentially all next states). The implementation achieves this

exploration in a \emph{breadth-first search} manner. 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:

  case c::cs => next(q, c).exists(search(_, cs)) 

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

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

some regular expression matchings in Java, Ruby and Python. I like to

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 uses the non-determinism in

NFAs. 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: an

$\epsilon$-transition means you do not have to ``consume'' any part of

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

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

either to $Q_1$ or $Q_2$. In this example you can see that once you

are in $Q_1$, respectively $Q_2$, you cannot ``go back'' to the other

states.

On first appearances, $\epsilon$-transitions might 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, 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---we are not really

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

translating regular expressions into automata. We are not going to

implementing them explicitly, but translate them directly into NFAs

(in a sense $\epsilon$NFAs are just a convenient API for lazy people).

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 left-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 the $\epsilon$-transition is replaced by

three more $a$-transitions. So whenever we are given $\epsilon$NFA we

will, similarly, replace it by an equivalent NFA. The code for this is

given in Figure~\ref{enfa}. At the core is a function that calculates

a fixpoint of function (Lines 5--10). This is used for ``discovering''

states reachable by $\epsilon$-transitions. Once no new state is

reachable state, a fixpoint is reached. This is used for example when

calculating the starting states of an equivalent NFA---see Line 36.

We starts with all starting states of the $\epsilon$NFA and then look

for all other states that can be reached by

$\epsilon$-transition. This is what the $\epsilon$-closure, called

\texttt{ecl}, calculates.

\begin{figure}[p]

\small

\lstinputlisting[numbers=left,linebackgroundcolor=

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

                  {../progs/enfa.scala}

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

Now having a translation of $\epsilon$NFAs to NFAs in place, we can

finally make headway with the problem of translating regular

expressions into equivalent NFAs. By equivalent we mean that the NFAs

recognise the same language. Consider the simple regular expressions

$\ZERO$, $\ONE$ and $c$. They can be translated into equivalent NFAs

as follows: