26 Java are so slow with certain regular expressions.

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

    27 also see what are the limitations of regular expressions.

    31 The central definition is:\medskip

    32 Lets start\ldots the central definition is:\medskip

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

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

   110 ``delta-hat''. Given a string, we start in the starting state and take

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

   111 the first character of the string, follow to the next state, then take

   112 take the first character of the string, follow to the next state, then

   112 the second character and so on. Once the string is exhausted and we

   113 take the second character and so on. Once the string is exhausted and

   113 end up in an accepting state, then this string is accepted by the

   114 we end up in an accepting state, then this string is accepted by the

   117 with this case elegantly by using Scala's \texttt{Try}. So a string

   118 with this case elegantly by using Scala's \texttt{Try}.  Summing up: a

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

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

   135   construction by lifting the transition (partial) function to

   136   construction by lifting the transition (partial) function to lists

   136   lists of characters. Since \texttt{delta} is given

   137   of characters. Since \texttt{delta} is given as a partial function,

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

   138   it can obviously go ``wrong'' in which case the \texttt{Try} in

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

   139   \texttt{accepts} catches the error and returns \texttt{false}---that

   139   returns \texttt{false}---that means the string is not accepted.

   140   means the string is not accepted.  The example \texttt{delta} in

   140   The example \texttt{delta} implements the DFA example shown

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

   141   earlier in the handout.\label{dfa}}

   142   handout.\label{dfa}}

   144 My take of a simple Scala implementation for DFAs is given in

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

   154 reason for having polymorphic types for the states and the input of

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

   155 DFAs will become clearer later on.)

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

   156 

   157 

   157 The most important point in this implemnetation is that I use Scala's

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

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

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

   161 supposed to return true whenever a state is final; false

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

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

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

   165 functions for final states, rather than sets.

   166 

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

   179 \noindent I let you think what this DFA looks like in the graphical

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

   180 notation.

   190 graph notation.

   181 

   191 

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

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

   183 implementation it not a set of states, as in the matemathical

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

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

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

   185 supposed to return true whenever a state is final; false

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

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

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

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

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

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

   189 functions for final states, rather than sets.

   190 

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

   192 doing so I hope you notice that the $\varSigma$ and $Qs$ components (the

   193 alphabet and the set of finite states, respectively) are missing from

   194 the class definition. This means that the implementation allows you to

   195 do some fishy things you are not meant to do with DFAs. Which fishy

   196 things could that be?

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

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

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

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

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

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

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

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

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

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

   208 Qs, Q_{0s}, F, \rho)$ where

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

   249 There are a number of additional points you should note with

   252 There are a number of additional points you should note about

   262 and I also do not use transition functions that return sets of states

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

   263 (another popular choice for implementing NFAs).  For reasons that

   266 partial transition functions that return a single state; my NFAs

   264 become clear in a moment, I use sets of partial functions

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

   265 instead---see Line 7 in Figure~\ref{nfa}. DFAs have only one such

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

   266 partial function; my NFAs have a set.  Another parameter,

   269 mathematical definition of NFAs.

   267 \texttt{starts}, is in NFAs a set of states; \texttt{fins} is again a

   270 

   268 function from states to booleans. The \texttt{next} function

   271 Like in the mathematical definition, \texttt{starts} is in NFAs a set

   269 calculates the set of next states reachable from a single state

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

   270 \texttt{q} by a character~\texttt{c}---this is calculated by going

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

   271 through all the partial functions in the \texttt{delta}-set and apply

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

   272 \texttt{q} and \texttt{c} (see Line 13). This gives a set of

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

   273 \texttt{Some}s (in case the application succeeded) and possibly some

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

   274 \texttt{None}s (in case the partial function is not defined or produces an

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

   275 error).  The \texttt{None}s are filtered out by the \texttt{flatMap},

   278 just lifts this function to sets of states.

   276 leaving the values inside the \texttt{Some}s. The function

   279  

   277 \texttt{nexts} just lifts this function to sets of

   278 states. \texttt{Deltas} and \texttt{accept} are similar to the DFA

   279 definitions.

   280 

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

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

   287   Notice some subtleties: Since \texttt{delta} is given

   286   Notice that the function \texttt{accepts} implements the

   288   as a set of partial functions, each of them can obviously go ``wrong'' in which

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

   289   case the \texttt{Try}. The function \texttt{accepts} implements the

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

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

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

   291   way of deciding whether a string is accepted in practical contexts.\label{nfa}}

   294 The reason for using sets of partial functions for specifying the

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

   295 transitions in NFAs has to do with pattern matching. Consider the

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

   296 following example: a popular benchmark regular expression is

   297 $(.)^*\cdot a\cdot (.)^{\{n\}}\cdot b\cdot c$. The important point to

   298 note is that it uses $.$ in order to represent the regular expression

   299 that accepts any character. A NFA that accepts the same strings as

   300 this regular expression (for $n=3$) is as follows:

   301 

   302 \begin{center}

   303 \begin{tikzpicture}[>=stealth',very thick, auto, node distance=7mm,

   304     every state/.style={minimum size=0pt,inner sep=1pt,

   305       draw=blue!50,very thick,fill=blue!20},scale=0.5]

   306 \node[state,initial]  (Q_0)  {$Q_0$};

   307 \node[state] (Q_1) [right=of Q_0] {$Q_1$};

   308 \node[state] (Q_2) [right=of Q_1] {$Q_2$};

   309 \node[state] (Q_3) [right=of Q_2] {$Q_3$};

   310 \node[state] (Q_4) [right=of Q_3] {$Q_4$};

   311 \node[state] (Q_5) [right=of Q_4] {$Q_5$};

   312 \node[state,accepting] (Q_6) [right=of Q_5] {$Q_6$};

   313 \path[->] (Q_0) edge [loop above] node  {$.$} ();

   314 \path[->] (Q_0) edge node [above]  {$a$} (Q_1);

   315 \path[->] (Q_1) edge node [above]  {$.$} (Q_2);

   316 \path[->] (Q_2) edge node [above]  {$.$} (Q_3);

   317 \path[->] (Q_3) edge node [above]  {$.$} (Q_4);

   318 \path[->] (Q_4) edge node [above]  {$b$} (Q_5);

   319 \path[->] (Q_5) edge node [above]  {$c$} (Q_6);

   320 \end{tikzpicture}

   321 \end{center}

   322 

   323 \noindent

   324 Also here the $.$ stands for accepting any single character: for example if we

   325 are in $Q_0$ and read an $a$ we can either stay in $Q_0$ (since any

   326 character will do for this) or advance to $Q_1$ (but only if it is an

   327 $a$). Why this is a good benchmark regular expression is irrelevant

   328 here. The point is that this NFA can be conveniently represented by

   329 the code:

   330 

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

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

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

   334   { case (Q0, 'a') => Q1 },

   335   { case (Q0, _)   => Q0 },

   336   { case (Q1, _)   => Q2 },

   337   { case (Q2, _)   => Q3 },

   338   { case (Q3, _)   => Q4 },

   339   { case (Q4, 'b') => Q5 },

   340   { case (Q5, 'c') => Q6 }

   341 )

   342 

   343 NFA(Set[State](Q0), delta, Set[State](Q6))

   344 \end{lstlisting}}

   345 

   346 \noindent

   347 where the $.$-transitions translate into a

   348 underscore-pattern-matching. Recall that in $Q_0$ if we read an $a$ we

   349 can go to $Q_1$ (by the first partial function in the set) and also

   350 stay in $Q_0$ (by the second partial function). Representing such

   351 transitions in any other way in Scala seems to be somehow awkward; the

   352 set of partial function representation makes them easy to implement.

   353 

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

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

   357 to go to is not unique anymore with NFAs). The implementation achieves

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

   358 this exploration in a \emph{breadth-first search} manner. This is fine

   296 potentially all next states). The implementation achieves this

   359 for very small NFAs, but can lead to problems when the NFAs are

   297 exploration in a \emph{breadth-first search} manner. This is fine for

   360 bigger. Take for example the regular expression $(.)^*\cdot a\cdot

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

   361 (.)^{\{n\}}\cdot b\cdot c$ from above. If $n$ is large, say 100 or

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

   362 1000, then the corresponding NFA will have 104, respectively 1004,

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

   363 nodes. The problem is that with certain strings this can lead to 1000

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

   364 ``active'' nodes in the breadth-first search, all of which we need to

   302 implementation we can implement a depth-first version of

   365 analyse when determining the next states. This can be a real memory

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

   366 strain in practical applications. As result, some regular expression

   367 matching engines resort to a \emph{depth-first search} with

   368 \emph{backtracking} in unsuccessful cases. In our implementation we

   369 can implement a depth-first version of \texttt{accepts} using Scala's

   370 \texttt{exists} as follows:

   377   case c::cs =>

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

   378     delta.exists(d => Try(search(d(q, c), cs)) getOrElse false)

   381 def accepts(s: List[C]) : Boolean = 

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

   387 examples and is much less of strain on memory. The problem is that the

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

   388 backtracking can get ``catastrophic'' in some examples---remember the

   320 the backtracking can get ``catastrophic'' in some examples---remember

   389 catastrophic backtracking from earlier lectures. This depth-first

   321 the catastrophic backtracking from earlier lectures. This depth-first

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

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

   407 In order to get an idea what calculations are done in Java \& friends,

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

   408 we need a method for translating regular expressions into

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

   409 automata. The simplest and most well-known method is called

   331 an automaton. This automaton should accept exactly those strings that

   410 \emph{Thompson Construction}, after the Turing Award winner Ken

   332 are accepted by the regular expression.  The simplest and most

   411 Thompson who implemented this method in early versions of grep????

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

   412 

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

   413 

   335 recursion over regular expressions and uses the non-determinism in

   414 The reason for introducing NFAs is that there is a relatively

   336 NFAs. You will see shortly why this construction works well with NFAs,

   415 simple (recursive) translation of regular expressions into

   337 but is not so straightforward with DFAs. Unfortunately we are still

   416 NFAs. Consider the simple regular expressions $\ZERO$,

   338 one step away from our intended target though---because this

   417 $\ONE$ and $c$. They can be translated as follows:

   339 construction uses a version of NFAs that allows ``silent

   340 transitions''. The idea behind silent transitions is that they

   341 allow us to go from one state to the next without having to consume a

   342 character. We label such silent transition with the letter

   343 $\epsilon$ and call the automata $\epsilon$NFAs. Two

   344 typical examples of $\epsilon$NFAs are

   345 

   346 

   347 \begin{center}

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

   349 \begin{tikzpicture}[>=stealth',very thick,

   350     every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

   351 \node[state,initial]  (Q_0)  {$Q_0$};

   352 \node[state] (Q_1) [above=of Q_0] {$Q_1$};

   353 \node[state, accepting] (Q_2) [below=of Q_0] {$Q_2$};

   354 \path[->] (Q_0) edge node [left]  {$\epsilon$} (Q_1);

   355 \path[->] (Q_0) edge node [left]  {$\epsilon$} (Q_2);

   356 \path[->] (Q_0) edge [loop right] node  {$a$} ();

   357 \path[->] (Q_1) edge [loop right] node  {$a$} ();

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

   359 \end{tikzpicture} &

   360 

   361 \raisebox{20mm}{

   362 \begin{tikzpicture}[>=stealth',very thick,

   363     every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

   364 \node[state,initial]  (r_1)  {$R_1$};

   365 \node[state] (r_2) [above=of r_1] {$R_2$};

   366 \node[state, accepting] (r_3) [right=of r_1] {$R_3$};

   367 \path[->] (r_1) edge node [below]  {$b$} (r_3);

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

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

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

   371 \end{tikzpicture}}

   372 \end{tabular}

   373 \end{center}

   374 

   375 \noindent

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

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

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

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

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

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

   382 states.

   383 

   384 On first appearances, $\epsilon$-transitions might look rather

   385 strange, or even silly. To start with, silent transitions make the

   386 decision whether a string is accepted by an automaton even harder:

   387 with $\epsilon$NFAs we have to look whether we can do first some

   388 $\epsilon$-transitions and then do a ``proper''-transition; and after

   389 any ``proper''-transition we again have to check whether we can do

   390 again some silent transitions. Even worse, if there is a silent

   391 transition pointing back to the same state, then we have to be careful

   392 our decision procedure for strings does not loop (remember the

   393 depth-first search for exploring all states).

   394 

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

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

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

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

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

   400 NFAs. Next, show that the $\epsilon$NFAs are equivalent to NFAs and so

   401 on. Once we have done all this on paper, we would need to implement

   402 $\epsilon$NFAs. Lets try to take a shortcut---we are not really

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

   404 translating regular expressions into automata. We are not going to

   405 implementing them explicitly, but translate them directly into NFAs

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

   407 How does the translation work: well we have to find all transitions of

   408 the form

   409 

   410 \[

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

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

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

   414 \]

   415 

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

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

   418 the NFA

   419 

   420 \begin{center}

   421 \begin{tikzpicture}[>=stealth',very thick,

   422     every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

   423 \node[state,initial]  (r_1)  {$R_1$};

   424 \node[state] (r_2) [above=of r_1] {$R_2$};

   425 \node[state, accepting] (r_3) [right=of r_1] {$R_3$};

   426 \path[->] (r_1) edge node [above]  {$b$} (r_3);

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

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

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

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

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

   432 \end{tikzpicture}

   433 \end{center}

   434 

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

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

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

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

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

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

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

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

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

   444 for all other states that can be reached by

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

   446 \texttt{ecl}, calculates.

   447 

   448 \begin{figure}[p]

   449 \small

   450 \lstinputlisting[numbers=left,linebackgroundcolor=

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

   452                   {../progs/enfa.scala}

   453 

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

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

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

   457   for a ``proper'' transition. The functions in Lines 18--26 calculate

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

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

   460 \end{figure}

   461 

   462 

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

   464 finally make headway with the problem of translating regular

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

   466 recognise the same language. Consider the simple regular expressions

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

   468 as follows:

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

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

   797 $Q_2$, and the secont that being in $Q_2$ and consuming an $a$

   857 $Q_2$, and the second that being in $Q_2$ and consuming an $a$

   818 \noindent where in Equation (4) we have two occurences

   878 \noindent where in Equation (4) we have two occurrences