Your about to embark on the study of the branch of computer science theory know as
automata theory or language theory. We're going to follow fairly closely a one
quarter course I gave at Stanford a few years ago. It's traditional number CS154.
This theory plays an important role in computer science. I'm aware that many
students do see the importance to the mathematical approach to CS, the feeling
is just let me near a keyboard and let me code, It's quite common. In this
introductory video I'll try to give some reasons why you should learn the material
contained in the course. A number of years ago Stanford took a survey of its
graduates five years after they got their undergraduate degrees. What they wanted to
find out was whether Stanford was teaching stuff that they actually used in their
jobs. So computer science graduates naturally sided out in conducting
programming courses as the one they used the most, No surprise here. Next came our
sophomore level course, covering basic data structures and algorithms and system
software, Again no surprise. But after the required courses, we found the CS154, the
automata course on which this set of videos is based was second after the
database course. It was cited by three times as many as cited the introductory AI
course, for example, So I want, in the next few minutes, to try to explain what
it was about automata theory that impacted what our former students were doing in
their professional lives. So, let's see some of the ideas we are going to learn
about in the course and how they appear in practice. One very commonly used idea is
the regular expression, A simple notation for describing many of the patterns that
arise naturally in practice. Many pieces of software that you might find yourself
working on in the future need a simple input language to describe patterns. So
you might well find yourself implementing some form of regular expression. For
example, many UNIX text processing commands use a variety of regular
expressions. This expression describes a line of text that has a letter A followed
by any number of characters followed by the letter B. For a more modern example,
the XML document mark-up language invites us to describe the structure of documents,
by a DTD, or document type definition. The DTD language consists of description
development, such as the example given here. A person element consists of a name
element, followed by an address element, followed by any number of child elements.
Finite automata are another topic we'll see early on, They are in fact the way
regular expression based languages are implemented. They also have been used for
decades to model electronic circuits, and in particular to help design good
circuits. They have also been used to model protocols, and we'll give some
examples later in this course. Especially [inaudible] underlie the body of
techniques known as model checking, Which has been used to verify the correctness of
both communication protocols and large electronic circuits. Another important
aspect of the course is the context free grammar. These are used to put a tree
structure on strings, typically text strings, according to some recursive
rules. They are an essential for describing the syntax of programming
languages and are a part of every compiler. They also play an important role
in describing the syntax of natural languages and are used in software that
does machine translation and other natural language processing. And the DTD as we
mentioned in connection with regular expressions are really context free
grammars. It is the single rules of the DTD that look like regular expressions. .
The topics we just mentioned are essentially tools for doing simple but
important things but there's a second broad theme in this course. There are
fundamental limitations on our ability to compute. A computer scientist should be
aware of these limitations because only then can you avoid spending time
attempting something that is impossible. Mm-hm. One limitation is undecidability
there are problems that cannot be solved by computation. For example you might
imagine you could, could right a compiler that would refuse To compile programs that
printed out dirty words. Even assuming you had a precise definition of what words
were dirty. You can't do this. We're going to prove that there is no way to tell
whether a program will ever print a particular word Or even if it will ever
print anything at all. And we also need to know about the classic problems called
intractable. These are colloquially problems that we can solve but whose
solution takes time that is exponential in the input size. These problems generally
need To be finessed in some way such as by approximating the solution. The reality of
the theory of intractability is quite a bit different from the colloquial version.
But while the undecidable problems have been proven not to have any solution, for
the attractable problems we have very strong evidence that they require an
exponential time but no proof. We'll explain all this when we get to the theory
of NP completeness is the culmination of this course. So another thing you will
take away fomr this course is the ability to navigate the space of problems that you
might encounter in a life of creative software construction. You will learn to
learn how to determine that a problem is undecidable, and how to determine that it
is intractable. That lets you avoid the problem altogether in the first case, and
to modify your approach in the second case. There's several less concrete
benefits to this course. First you will improve your skills at proving fact,
especially inductive proofs of which we'll do several in great detail. Now I'm not
one of the people who thinks formal proofs of programs will ever be a serious
software methodology, but as you construct code you should have a sense of why what
you're doing works, the way it is suppose to. Often the trickiest parts of a program
deal with trees, graphs, or other recursive structures. Understanding
inductive proofs let you at least formulate a reason why you think your
method works, even if you don't try to dot the I's in a formal proof. We're also
going to learn about a number of important abstractions: finite automata, regular
expressions, context-free grammars, and varieties of pushdown automata and Turing
machines. Some of the essential parts of this course are proving equivalences among
the models, that is, any example of one model can be simulated by some instance of
another model. The process of simulation across the models is essentially the same
as the modern approach to programming and layered abstractions where you write
programs at one layer, using the primitives of the layer below. At
Stanford, I found that a number of people taking the automata course were not
computer scientists at all, but were mathematicians [inaudible] by inclination.
That's cool. Welcome to those of you out there. I probably won't do things quite as
formally as you would like, but more formally then the typical computer
scientist likes. However, be warned that some in the past have found the subject
sufficiently interesting, that they saw the light, and made major contributions to
computer software. A case in point is Ken Thompson, the fellow who gave us Unix.
Before doing Unix, Ken developed an interest in regular expressions and saw
that they were an important part of the text, text editor. He worked out efficient
ways to compile regular expressions into programs that could process text. And his
algorithms are an important part of what we teach about the subject today. It
should be no surprise that regular expressions form an integral part of so
many Unix commands, and that these commands give more flexibility and power
to Unix users than did those of earlier operating systems. Another interesting
case is Jim Gray. Jim, before his mysterious disappearance, gave us many
important ideas in the database field, including two phase locking for
concurrency control for which he won the Touring Award. But I knew Jim when he was
a student at Berkeley and I was on leave there for a brief period. He did a thesis
on two way pushed on automata. We're not going to talk about them. They turned out
to have been back water of the theory and I am sure Jim would agree but they're
related to ordinary pushed down automata which we will talk about in connection to
context regrammars. What is interesting is that Greg told me quite a bit later that
he decided to become a computer scientist because automata theory intrigued him.
Only later did he switch into database systems, and I believe that the experience
he got the aloof fumbling with automata make him more capable as a designer of
several very innovative systems. So here's a summary of what will be covered in the
course. We'll start off with what I called regular languages. A language is just a
set of strings, for example the set of character strings that are valid java
programs. The regular languages are exactly those sets of strings that can be
des, described by finite [inaudible] or regular expressions. This discussion will
also introduce the important concept of nondetermism. Machines that can magically
turn into many machines that each do something independently but with a
coordinated effect. This model of computation is fanciful, to say the least,
but we'll see it plays a really important role in several places, including design
of algorithms and in understanding the theory of intractable problems. We're then
going to turn to properties of the regular languages. These properties include the
ability to answer certain questions about finite automata and regular expressions
that we cannot decide about programs in general. An example would be to tell
whether a device makes an output in response to even one input. You can't tell
for programs in general, but you can for finite automata. It is distractibility Our
ability to understand very simple formula sums, like finite automata or regular
expressions do, that make them so very valuable when they can be used. We're also
gonna talk closure properties of regular languages for example the union or
intersection of two regular languages is also a regular language. The next big
topic will be context free languages. This is a somewhat larger class of languages
that the regular languages. And they enable us to do things that you can't do
with regular languages such as mash balance parentheses or XML tags. We'll
talk about two ways to describe such languages. First by context-free grammars,
A recursive system, system for generating strings. And then by pushdown automata,
Which are, are a generalization of the finite automata that we'll use for regular
expressions. We'll then repeat our examination of decision properties and
closure properties for this larger class of languages. Many of the things we can
tell about regular languages that we cannot tell in general, we can also tell
about context free languages. But there are unfortunately some exceptions.
Similarly, many of the operations under which regular languages are closed, also
yield a context free language when applied to context free languages. But again we
lose some operations for example context free languages that close in reunion but
not intersection. Next we take up the largest class of languages that we can
reasonable say can be dealt with by a computer and recursively enumerable
languages. We also look at the smaller but important subset of the recursively
enumerable languages, called the recursive languages. These are the languages for
which there is an algorithm to tell whether or not a string is in the
language. We introduce the Turing machine, an automaton in the spirit of the first
kinds of automata we meet, finite and pushdown automata. The Turing machine is,
however, much more powerful than either of these. In fact, it is as powerful as any
model that has ever been thought of to answer the question, what can we compute?
The payoff of the study of Turing machines is that we can answer the question of what
can be decided by computation, or what can be computed by any means at all. We shall
develop tools for showing that certain problems cannot be decided. That is
answered by computer. The example we already mentioned is a program print dirty
word should give you an idea of what we can achieve. Finally regard to cover the
theory of NP completeness, the critical question is what can we do with an
algorithm that runs in time that is some polynomial and a link of the input. It
would be lovely if we could distinguish between problems as best algorithm took
say in cubic time from those that can be solved say in squared time. But no theory
has ever been devised to be that precise for general problems. Although the best
running time for some problems is null, fortunately we can learn a lot by dividing
problems that can be solved in some polynomial amount of time from those that
apparently require exponential time. We'll give you the tools to do this, and Turing
machines are the tool you need to build this theory as well as the theory of what
can be computed at all. This course follows the third edition of the textbook
I wrote with John Hopcroft and Rajeev Motwani. You do not need to buy this book.
The homeworks and exams will all be based on what you can learn by observing The
slides and listening to my commentary on the slides. Okay. The following is
optional, and depends on what we decide to do about, the page references and the
hallmarks. You will incidentally find as you do the hallmarks that there are
explanations when you make a mistake. These explanations refer to pages of
sections in this book. But you do not need the book since the explanations like the
course material itself, are designed to be self contained without your having to read
the book. I ask one thing however, please do not download a free copy from a file
sharing site, or delete it if you have already done so. This book was published
by Addison Wesley under a contract that dates back to 1967. At that time there was
no internet, and it wasn't all that easy to produce books. Addison Wesley invested
a good deal in the production of this book and its predecessors, and they deserve to
recover their costs. It is stealing to download a copyrighted work without
paying. There's no two ways to look at it. Admittedly the world has changed, and
recently I've started to put books on the Web for free download from my own Stanford
Webpages. You are welcome to what is freely given, but please do not take what
is not offered gratis.