So the final step in our regular
refreshing pattern matching algorithm is
to construct and then determine the thick
finite automaton. So how do we go ahead
and do that? and this is an integral part
of the algorithm. but we pretty much have
got all the pieces, but really what makes
it intricate is that if, an illustration
of what a programming line has to do to
when trying understand your program, what
your programming does. What we need to do
is somehow understand what's in the
regular expression and then take that
information and use it to build the
machine. Now, that's what parson, that's
called parsoning. to try to figure out the
structure of your program or regular
expression and then, do something with it.
And this is a simple example of that but
useful as well. So the first thing that
needs clear what to do. So we're going to
have one state per character as we talked
about before, so that's easy to set up.
and then the match transition edges. if a
state contains a character in the
alphabet, we just put in a match
transition to the next state. and
actually, that's implicit in our
algorithm. so now what about other things?
Well, if we have for any parenthesis we
find, we'll just put in an epsilon
transition to the next state. so our
machines all have that. now closure is one
that you know, has quite a bit of action.
so, for every star let's look at the one
that is just a one character closure. So
we have a single character closure. So
this is A star. and, and what we need is
epsilon transitions for the star that
allow the machine to go and pick up well,
there has, there has to be one, an epsilon
transition that goes out to the star to
cover the case, so we have zero matches.
and then after zero, then we want to go
back to have as many matches as we want
before taking the sorry, take the match
transition. We're going to be able to go
back and match as many as we want before
going up to the next. So for star, we have
to add three epsilon transitions. The one
that goes if you have a character in I and
a star in I + one , you have to add these
edges going both ways and then an edge out
to the next character for, to get out of
the star. And that works also if there's a
closure involving parentheses. If the
character before the star is a parenthesis
then we want to add the same kind of
mechanism from the parenthesis, go out and
skip the whole thing to cover the zero
match case or go back and match as many
times as we need to match and then
finally, go out. So there's three edges
have to be added for each star and defined
and well defined what they are. and then
or there's two epsilon transition edges
that we have to add. and that is to allow
the machine to skip the first part of the
expression and do the second or to skip
the, do the first part of the expression
and skp the second. so if we keep track of
where the left parenthesis is when we end
the or operator when we get to the right
parenthesis, we have all the information
that we need in order to be able to add
those two edges. so those are the edges
that we have to put together to build the
NFA. and the trick is keeping track of the
information of where the previous
operators are particularly since
parentheses can be nested. but this is not
that difficult to do because we have a
mechanism for doing that. how to, to,
remember where the left parentheses are
and, and the or and that's to maintain a
push down stack. and so the, the algorithm
is to push left parenthesis in or onto the
stack. And then when we hit right
parenthesis, then we can pop of course the
corresponding left parenthesis and maybe,
maybe the or and that gives us all the
information that we need to add the
epsilon transition edges and so the stack
takes care of the nesting of the
parenthesis. and when you think about it,
this is a very natural mechanism to use
very similar to the early programs that we
wrote using Dexter's algorithms for medic
expressions. so let's look at a demo and
you'll see how that works. So we're going
to build the machine corresponding to this
regular expression and it's the one that
we've been working with. And so what we do
is just go from left to right through the
regular expression and , take the
appropriate action, for each character. So
for left parenthesis. there's always an
epsilon transition from, left parenthesis
to the next state. and then the other
thing is, if you remember that last
parenthesis on the push down stack. So we
put the index zero onto the stack. so now
we got another left parenthesis again, we
put the epsilon transition on, and we push
that one onto the stack. so now, if we
have an alphabet symbol what we need to do
is add the match transition to the next
state. And then there's a couple ways to
this, but one easy way, in this case, is
to just look for the star and if you see
that the next one is a star then you've
got everything you need for the epsilon
transitions. So, in this case the next one
is a star so we'll add those epsilon
transitions from the from two to three and
from three to two.
And adding epsilon transitions, that's
just, adding edges to the phi graph. then
with closure that just takes us to the
next state and we took care of the other
two earlier. now we have an alphabet
symbol, that's the B, so we just put in
the transition to the next state. Now we
have an or. All we do for an or is put it
on the stack. now it's got for A, we got
the match transition, for C, we got the
match transition. and now we have the
first right parenthesis. so this right
parenthesis so one thing we, the first
thing we do is an epsilon period just to
get it over to the next state. but then we
go to the put down stack and we pop. and
if the thing at the top of the stack is an
or that's one thing, piece information
that we need. the other piece of
information we need is the position of the
corresponding left parenthesis and that'll
be the next thing on the stack. So we add
the transition we pop the or off the stack
and we pop the or on and off the stack and
that gives us the information that we need
to put in the epsilon transition. We're at
stage eight.
We put one from the or to eight, and then
we put one from the one to the or + one.
There's the, that's what we need to do.
and, look for a star the same way as we
did for one character. now in this case we
have a no star. So we just do the finite
alphabet symbol and we add the match
transition. and now we have the right
parenthesis and so we pop the
corresponding left parenthesis. and it's
not an or. so in this case you know,
there's nothing to do except do the
epsilon transition to the accept state. so
that's the process for each character in
the regular expression, it's well defined
what we do. left parenthesis and or we put
onto the stack characters we do the match
transitions and right parenthesis we do a
pop and if it's an or, put a numeric
transitions. otherwise we do the look at
to check for the star. and that's the demo
of the construction for nondeterministic
finite state of phenomena. So, it's
actually a remarkably simple process. we
figured out what to do with each character
in the regular expression and this is the
second part of the regular expression
pattern-matching algorithm, which is
constructing the NFA. And again it's a
remarkably little code. So it's a routine
that builds the epsilon transition. this
is a part of the NFA. So it's got the
regular expression . yes, a useless
variable to refer to. and it's going to
build a new diagraph with one state, one
extra state, the accept state M+11 if the
rate description has M characters. so, the
and then we maintain a stack which is just
integers. and for every character in a
regular expression we do the processing
that we just described. if it's a left
parenthesis or an or we just put it on to
the stack. and that's it. if it's a right
parenthesis then we pop. If that pop is an
or, then we put in the two edges to skip
the or. and otherwise, we look ahead and
do the closure exactly as described. If
it's any one of the metal symbols, we just
put in a next line transition to the next
edge. And then a remarkably little code to
go ahead and construct the NFA from a
given regular expression. and so, the
final step is the analysis that's going to
take time and space proportional to M. and
that's immediate, because for every
character we do most of two stack
operations and add at most three epsilon
transitions. And, this is a generous upper
bound, time and space proportional to the
number of characters in the regular
expression. So that's how we get the NFA