So that's a regular expression, pattern-matching that we implement by
constructing and simulating a nondeterministic finite state machine.
Really, one of the most ingenious algorithms that we look at in this course.
next we'll look at some applications. so, the most famous is called, Grep and this
is what Ken Thompson implemented in the initial Unix. And it was a very, very
important tool for programmers working on the tiny really tiny, computers that were
available at that time. it was really important to be able to ask questions
about programs of this type. and it allowed the development of bigger and
bigger computational infrastructure like the Unix Operating System that's still
widely used today. so Grep was a simple command. what you want to do is take a
regular expression as a command line argument and print the lines from standard
input to have some substring that's matched by the regular expression.
Programmers use that all the time to try to figure out what variables they use in
what part of what programming. many programmers, use Grep every day still
today. and here's how we implement it using the code that you know, we've talked
about so far. so first thing is, is create the RE that we're going to match to make
it more like subscreen search. We just care for the things in there anywhere at
all. So we put a dot star before and after and we enclose it in parenthesis just cuz,
cuz our code simplified, if our RE's enclosed in parenthesis. Build an NFA from
that regular expression. and then as long as there's an align in standard input, we
read the line and we ask if the NFA recognizes it. So the constructor builds
the NFA and recognizes is the simulation. if one NFA on that string, if it's there,
you print it out. if it doesn't recognize it the final accept state is not in the
substrateq you could get to, for that string, it won't print it out. And we just
do that for every line in the input. pretty, amazingly simple implementation,
although, quite elegant, conceptually. It's a very, Elegant, and, and, ef ficient
permutation of this basic process. Absolutely correct. so, in the bottom line
for it is in the worst case it's the same as for the, elementary substring search
algorithm that we looked at when we first started talking about string searching and
it's really amazing. the brute force algorithm that you come up with of
tri-matching the string, the single string at every character position. The worst
case is time proportional to M times N. But here we have a regular expression
which specifies an infinite set of patterns. And we can tell if any one of
those infinite set of patterns is matched by our string in the same worst case kind.
it's really an amazing algorithm that's Ken Thompson, Grep. Once you have Grep
available, then crossword puzzles become a lot easier. a lot of it's standard in UNIX
to a dictionary or if you can't find one on your system, we have it on the book
site that simply has all the words on the dictionary, all the lower case one per
line. and if you have a crossword puzzle where you're missing a couple of letters
you can just Grep for in words.txt for and, and leave, don't care is for those
letters, and it'll tell you the, the things you can put in there. In this case
it's the one that has exactly that many letters. It's stricter. so that's a
typical, application and I'm sure lots of people use it that way now. now for
industrial strength nowadays there's, a lot of things that people expect when
using regular expressions. our implementation doesn't have character
classes. it doesn't have the extra meta characters like plus and other things. the
idea of capturing which actually get the part of the string that satisfies, that
matches the regular expression of various different extensions of closure. and then
there's the idea of greedy versus reluctant matching. So, for example, if
you have a regular expression, blink. /blink which you'd find in HML for the
blinking text. there's two possibilities. so called reluctant matching would be like
the tightest match, matches that you'd get. You h ave two of them but then, the
greedy matching would get as much text as it possibly could in different
applications, you might want different things. Capturing means give me the
substring that matches. and so those things are not difficult to add to the
basic code that we've done and all that has to be in industrial strength
implementation. many programming systems have Grep that have all these sorts of
things. again originated, originated in Unix in the 1970s and nowadays, every
language has to have some kind of extended regular expression facility. there's,
language Unix commands like Grep and lock, and old programmer's tools like EAMCs.
There's modern programmer's tools like Perl or PHP Python and Javascript. All of
these things have regular expression processing. and so, programmers demand
this facility nowadays. in fact, Perl is an example of an entire language that's
built on regular expressions. and again there is various command line options you
can say run it for each line and you have replacement facilities and many other
things that is, is certainly a worthwhile facility for any programmer to use
nowadays and many programmers use these things. Now to, again to go back to the
slide that was filled up with a regular expression you want to use these things
wisely there are definitely computational tasks, where it might be better to just
write a Java program, not try to use a regular expression. So every tool has it's
place and try not to do everything with the regular expression language. in Java
various facilities, are built in to different parts of the Java library. and
so and understanding how the implementation works. you can understand
how to use these. so one simple, implementation is in the Java string
library. so if there's a, you have a string called input and another string
called regexp and the matches method in the string library will return the bullion
that says if the strings in the line which you know, described by the regular
expression. so this is just a simple stub that I call validate that takes a regular
expression and an input from the command line, unless you know if the, the, the
string is in the line that's described by the regular expression. So, like as I dent
one, two, three, and leave a little Java identifier giving that regexp legal Java
identifiers that we looked at earlier and so forth. so that's one thing that's built
in to Java. So in Java programs you can use regular expression pattern-matching in
that simple way. another thing, another kind of task that is better handled with a
that's handled with this Java implementation as the idea of harvesting.
so we want to print all the sub strings of the input that match a given RE. So, say
this is the fragile X syndrome we want to harvest all the patterns from the DNA
that, have this property that starts with gcg and ends with ctg and has any number
of these triple gcg or cth, triples inside. or maybe you want to harvest the
same program harvests all the e-mail addresses from a web page. That's kind of
amazing that the same program can work for two such diverse tasks. that's, that's a
testimony to the utility of this abstraction. so how do we do harvesting
within Java? Well it's got a, Java has two classes called pattern and matcher that
implement regular expression pattern-matching basically by, as we did,
separating the construction of the machine from the simulation. so this is what the
code looks like for harvester. We take our regular expression as the first command
line argument and we setup an input stream from the second command line argument, can
be a file or a webpage. and then we read the input stream. then we use Java's
pattern class, to, to build a pattern which essentially is an NFA that is
constructed from the regular expression. in the pattern class, has a method called
a matcher and that essentially creates an NFA stimulator from that NFA for that
text. and, so that's a machine that not only does matching in the way that we did,
but it also finds a match and keeps track of what's called group, which is the
substring that caus e the match. so it adds that extra code to do these things
that are useful in this illustrates one line of code for each one of those
facilities. That is, create the NFA, create the simulator find the next match
and get the substring that cause the match. That's an implementation of
harvester that can go through and do things like get fragile X indicators from
a chromosome or get e-mail addresses from a web page. And of course, you could
extend that to print out the index of where they occur and other things. this is
a very powerful facility to have in a programming language and Java certainly
has it. Now there is a caveat about this that's really important. this introduces
the idea that we talked about with hashing and this is another example of the
algorithmic complexity attack. And that is, if you know something about the way
that a website is implemented at facility. in this case, it's possible to implement
regular expression pattern-matching in a not so efficient way and atypically,
actually, the implementations that we see out in the wild like the ones in Unix or,
or Java or Perl, do not guarantee quadratic performance the way we have.
They do not guarantee the running time's going to be proportional to the product or
the length of the string and the length of the regular expression. In fact, they go
exponential. again, going back to Kleene's theorem, it's relatively simple to prove.
it's not so difficult to develop an implementation that is more like Kleene's
theorem, but it can take exponential time. and you can try it yourself in Java or
Perl, if you try to look for a match for this regular expression in a string like
that, you add just a couple of characters to the string then running time will
double. again, going back to our algorithmic performance lectures. if
that's what happens, if I just add one thing and my running time doubles that
means I have exponential time. and so if I'm using a facility that has one of these
exponential time implementations then, this is, what's called a SpamAssassin reg
ular expression. it's going to take exponential time on certain e-mail
addresses and, somebody can create trouble by sending such addresses to a mail server
the mail server will take exponential time just trying to determine if it's spam or
not. and by having an inefficient algorithm, a server like that is
definitely subject to such a tax. generally, you don't want to have
exponential algorithms you particularly don't want to have exponential algorithms
if you have arbitrary clients out there that can cause trouble for you. a another
pitfall is things that kind of look like regular expressions but aren't actually
regular expressions. So it's common to have the backslash one notation. So that's
supposed to match the self expression that was matched earlier. So this thing dot
plus back slash one is a string that is two copies of something, like couscous or
with at least one character. and this one is a similar one. This one actually is
number of ones is not prime. it matches, so you can write pretty sophisticated
computational thing just with these little references. but there's a problem and it's
a fundamental problem, is that . that kinds of languages of the sets of strings
that you specify with such notation are not regular. That is, like I said, it's a
point you can't write a regular expression to specify. and so these are examples like
strings to the form ww For sum W, you can't write a regular expression that,
will recognize, that will describe all such strings. There are even scientific
applications like complemented palindromes. So that's like a palindrome,
but also complements a's to t's and c's and g's. So that's another, example. And
if they're not regular, then Kleene's theorem doesn't hold. there's no NFA that
corresponds to them, and in fact we're, we'll talk in a couple of lectures about
intractability. in fact, nobody knows an efficient method for guaranteeing
performance when you have back references. so, if you're allowing back references
you're pretty much subject to performance attacks like the one we just mentioned.
and that's where, we'll will finish up this lecture. this is an amazingly
elegant, and efficient, and ingenious algorithm, and it's based on the theory of
computation that has been studied since the 1930's and it's the basis for much of
the programming, programming languages that we do. it's really worth
understanding this theory and Grep is a wonderful example of why it's important to
understand theory like this. it really it takes us to the next level of algorithms
and that's writing programs that translate a program to machine code. actually, what
we've looked at, both for KMP and for Grep are examples of compiler, they're simple
examples of compiler. for KMP, we took a string and we built a DFA. For Grep, we
took an RE and we built an NFA. and all Java C does is take Java language code and
translate it to a byte code. Now, it uses more complicated theorems and laws from
theory of computation to get the job done, because a java program is also not
regular. But, it really is worthwhile thinking about the progression from KMP to
a Java compiler. Whereas in Java compiler, you have a program, now, you want to
compile of and know if it's legal you want to get byte code and then you've got a
java simulator, and that's not so substantially different from what we just
did for Grep in a stage along the way. that's quite interesting to see this kind
of context to get us such a practically useful and important algorithm. so the
summary is we did some from the standpoint of the program, we implemented substring
search by simulating a DFA and we implement a regular expression
pattern-matching by simulating an NFA. from theoretician what's interesting about
these abstractions is that NFAs and DFAs and RE are equivalent in power. if you can
describe a set of strings for one of them, you could describe a set of strings with
any of them. so that's interesting. And also interesting is that there's
limitations, there's sets of strings like palindromes and so forth, that you can't
specify with a DFA or, o r an NFA. but from a student in an algorithms class it,
it really is you know, worthwhile to see that these principles are not just theory.
they're a practical use and this is an essential paradigm all throughout computer
science. you know, we want to find an intermediate abstraction that we can
understand and make sure we pick the right one, and then we pick clients that can use
it in a real implementations that can implement it. And by building the right
intermediate abstraction, we can solve some important practical problems. those
are the lessons that Grep teaches us.