Before we can get to the algorithm, we
have to consider another abstract concept
in the NFA and take a look at the NFA's
now. first of all, there's a duality, a
well-known duality between regular
expressions and DFAs. DFA is a discrete,
finite automaton. that's an abstract
machine from, theoretical computer
science. which is a very simple idea. It's
a state machine for recognizing whether a
given string is in a given set. And, if
you're not familiar with those, they are
very easy to understand and we'll, look at
some examples. in a little summary from
basic theoretical computer science,
there's a very important theorem called
Kleene's theorem that, was, developed
actually here at Princeton in the 30's and
it says that, for any discrete finite
state automaton, there exists a regular
expression that describes the same set of
strings. And equivalently, for any regular
expression, there's a DFA that recognizes
the same set of strings. and this is just,
an example. and if you have seen this,
this sort, this sort of thing will be
familiar and if we have, if you haven't
you know, and you will understand better
as we get into it. So, a discreet finite
state machine is a machine that has states
that are labeled and it has transitions
from state to state that are labeled with
characters. And, the way that it works is,
if it's in a state and it reads like for
every state is well defined is the next
character is zero or one it's another
state to go to. So for example at state
zero if you see a zero you stay in state
zero, if you see a one you go to state
one. In state one if you see a zero you
stay in state one, if you see a one you go
to state two, and so forth. So at every
state. read a character and go to the well
defined next state. That's a discreet a
deterministic final state automaton. and
so, that's the machine you start it up on
a string, and it reads all of the
characters in the string. and then, if it,
ends up in a state that's so called
terminal state, and started on the start
state the terminal state is just in
dicated by this X that are on this
example. It ends up in the right state you
say that it recognizes a set of strings.
and so that's a way to determine if a
given string is in a specified set. The
machine specifies the set. In an RE the,
we specify the set by writing characters
and stars and meta-characters in
parenthesis and this regular expression
recognizes these same set of strings.
Describes these set of same, same set of
strings that's recognized by this DFA.
Hank Leany's theorem showed that it's
always possible, to, construct such a
machine. So that gives a, a basic plan for
developing a pattern matching
implementation. and this is developed by
Ken Thompson at Bell labs, one of the
developers of UNIX, and, and this facility
was an important part of early UNIX and
developed this idea based on the
well-known theorem from theoretical
computer science. is let's try to build a
machine, the same way as we did for
Knuth-Morris-Pratt, where we have no
backup in the text input string. so we
just got a finite state machine. With
Knuth-Morris-Pratt we built a, a machine
for recognizing the one string how about
building one for multiple strings and that
would give us a linear time guarantee. so
the unruling extractions is determine if
it's FSA or DFA and the basic plan is to
just go ahead and take your pattern. It
describes a set of strings and use that to
build a DFA and then simulate the DFA with
the Texas input, the same way we did for
Knuth-Morris-Pratt And if it accepts, we
say we have a match. If it rejects, we
don't have a match. this is a, a fine plan
but it's got a flaw. the bad news is that
The plan is infeasible because the number
of states in the DFA might be exponential
in the length of the RE. So, for it's got
too many states Kleene's, the proof of
Kleene's theorem, standard proof of
Kleene's theorem , involves the
exponential number of states. and it's not
that difficult to prove if you're
interested be sure to look it up. But from
a practical, standpoint, too many states,
you can't use that as a basis for
algorithm. But there's an easy revision.
And again, this gets back. It will, it
will give us a quadratic time guarantee,
and actually, in, in real life, it's
usually linear, and all we do is change
the abstraction to use a non-deterministic
finite state machine, an NFA, rather than
a DFA. so, in the same basic plan, we're
going to build an NFA. It's a, it's a
different kind of machine, but actually,
it's also the case that, that, oh yeah.
For any regular expression we can build on
NFA so and in vice versa cleaning stand to
this and so we're going to simulate with
the NFA with the text as input. And so,
what do we, what do we mean by
non-determined as a finite state machine?
That's what we have to talk about next.
and we'll just do it with this example
that we used throughout this lecture. So,
It's very similar to the DFA that we have
before, now we're going to put the
characters in the states and actually, the
kind of NFA that we're going to build,
we're going to have one state for every
character in a regular expression. So this
is an NFA, corres-, corresponding to this
regular expression. just, to, We, we
always enclose the regular expressions in
parentheses. just to, make everything
work. and then, Got this regular
expression here. A star B or ACD. then,
we're going show how to build, this NFA.
and then, simulate it, to recognize the
regular expression. And, how is it
different than a DFA So, there's a
character in every state, and if the
character's a text character, it's the
same as before. We read that text
character and moved to the next state. But
it's a more general kind of machine,
because states also have what's called
epsilon transition. And with an epsilon
transition the machine is allowed to
change the state without scanning any
text. So, at the beginning the machine go
from zero to one, to two, back to one, I'm
sorry, two to three, back to two or it go
from zero to one over to six there's lots
of places the machine could go, without
scanning any text character. but we do
have the black matc h transitions that
scan text characters and so those are the
rules the machine operates by. And, the,
final rule is when does it accept, when
does it decide a strings in the pattern.
It accepts if there's any sequence of
transitions that scans all the text
characters and ends in the accept case.
it's a way of specifying an infinite set
of strings. but it's got this
non-determinism. It's not always
determined what the machine, will do next.
It's a little bit of a mind blowing
concept in theoretical computer science.
But this particular example actually shows
how such, such a concept can be made
concrete and actually give us a widely
useful algorithm. One way to think of a
non-deterministic machine is a machine
that has super powers and can guess the
proper sequence of state transitions to
get to the end. Get to the accept state.
another way to think about is the
sequences if you provide us particular
sequences that's a proof that the machine
accepts the text. and so this is a real
machine. We don't have a real machines
that can guess the right answer but it's a
completely well specified abstract
machine, and we can write a program to
stimulate it's operation, and that's what
we are going to do. So let's just make
sure that everyone's got the concept down.
So, say we have the question is 4A is
followed by BD, is that accepted by this
NFA down here? and the answer is yes
because there is a sequence of legal
transitions that ends up in state eleven.
So in this case, we'll take an epsilon
transition from zero to one to two and
then we'll... We've got 4A's so we'll chew
up four A's, one, tw-, I'm sorry. One, and
then go back. Two, and then go back.
Three, and then go back. Four, and then
we'll be in state three. And then at that
point, we'll decide to take this epsilon
transition. We'll assume your machine
decides to take this one. then it
recognizes the B and moves to state five.
And then, at state five, it no place to go
but to state eight. and then, takes the
epsilon transition to the state nine. It
recognizes the D that takes it out to ten
and eleven. So, there is a sequence of
state transitions that get to a eleven and
recognizes all the characters and the
strings, so therefore it's matched. what
about So the, It's true that there is
sequences that the machine might guess and
go to the wrong state or stall, it doesn't
matter as long as there's some sequence
and we are going to assume that the
machine always guesses the right one. So
for example, if the machine just
recognizes three A's, one, two, three, and
then went to state four, it would get
stuck because there's no way for it to get
out of state four because state four is
looking for a B, and it's sitting on an A,
and so forth. So, there's definitely,
things that the machine could do that
would be wrong, but we don't care, as long
as there's some way for it to get through.
and then, what about if it's a string
that's not in a language recognized by the
state. the machine, well, so we have to
argue about all possible sequences and,
prove that, no sequence of legal
transition, is transitions ends in state
eleven. and that, seems to be, a fairly
complicated sort of argument. So in this
case the machine could recognize a bunch
of A's, and then go to state four. But
again, there's no B, so there's no way
it's going to get out of state four. and,
so you can make a general argument like
looking at the machine that's any string
that it recognizes, it has to end in D and
this one doesn't end in D. that's a, much
more complicated thing, than we're talking
about, is to try to come up with, a,
simple machine that will decide whether or
not a string, is in the, language that it
specifies. so the question, so question
that we have is, we have this non
deterministic machine, how are we going to
decide whether a given string is in the
language that it recognizes. So for
deterministic machines, like we used for
Knuth-Morris-Pratt it's very easy, because
at every time, there's only one possible
transition. But for non-deterministic, if
you're, in some states, there's, multiple
ways to go, and you have to, figure out
the right transition. But actually, the
situation isn't so bad. and what we can do
is, to simulate the NFA, is just to make
sure that we consider all possible,
transition sequences. And that's what our
algorithm for a regular expression pattern
matching is going to be based on. that's
what we will look at next.