This page will be updated frequently.
Most recent update: April 28, 1999.
-
Background.
You will be assumed to know the contents of sections 1.1 through 1.4,
pages 3-27 of your textbook.
-
January 20, 1999.
The topics of today's lecture will be languages
(Section 1.5 of your textbook, pages 27-35) and proof
techniques, including induction, diagonalization, and the pigeonhole
principle (Chapter 2 of your textbook, pages 36-70).
-
Homework due.
Assignment 1
will be due on Monday, February 1, in class.
-
January 25, 1999.
The topics of today's lecture will be proof
techniques, including induction, diagonalization, and the pigeonhole
principle (Chapter 2 of your textbook, pages 36-70). We will discuss
the relationship between problems (such as the knapsack problem,
the traveling salesman problem, or the addition problem) and what it
means for a problem to be hard.
-
No textbooks.
Because the textbooks were not available in the bookstore before
Monday January 25,
the due date of Assignment 1 will be extended to Monday, February 1.
-
January 25, 1999.
The topics of today's lecture will include the concept of a machine
accepting a language. We will introduce finite automata
and possibly discuss regular languages. Read Chapter 3, pages
69-99 of your textbook.
-
January 27, 1999.
Today's lecture will continue of the topic of machines accepting languages.
We will introduce finite automata and regular languages and
regular expressions. Read Chapter 3, pages 69-99 of your textbook.
-
February 1, 1999.
Today's lecture will continue of the topic of machines accepting languages.
We will introduce non-deterministic finite automata, and show that the
class of languages they accept is also the class of regular languages.
Thus, for finite automata, non-determinism does not increase their
computational power. Read Chapter 4, pages 100-134 of your textbook.
If time permits, we will begin some of the material in Chapter 5,
pages 135-160 of your textbook.
-
Homework due.
Assignment 2
will be due on Monday, February 8, in class.
-
February 3, 1999.
Today's lecture will continue of the topic of regular languages and
finite automata.
We will show how to find a DFA equivalent to a given NFA, and also how
to find the minimal DFA equivalent to a given DFA.
We will introduce the pumping lemma, an important tool in
the dicussion of regular languages.
Be sure to finish reading Chapter 5 of your textbook.
-
February 8, 1999.
Today's lecture topic will be a continuation of the discussion of regular
langauges. We shall attempt to cover Chapter 5 of your textbook (pages
135-160). The major topic will be the Pumping Lemma.
-
Examination. We will have a short exam on February 10.
The exam will cover material up to, and including, Chapter 5 in your textbook.
As preparation for the examination, it might be wise to work a few
more parts of problem 5.35 on page 159 of your textbook.
(But do not hand them in.)
-
February 17, 1999.
Today's lecture topic will be a continuation of the discussion of context
free languages. We shall attempt to cover Chapter 6 of your textbook,
pages 163-197, but it is unlikely that we will finish that chapter today.
-
Homework due.
Assignment 3
will be due on Wednesday, February 24, in class.
-
February 22, 1999.
Today's lecture topic will be a continuation of the discussion of context
free languages. We continue with Chapter 6 of your textbook, pages 163-197.
We may be able to get to the Pumping Lemma today.
-
February 24, 1999.
Today's lecture topic will be pushdown automata (PDAs)
and their connection with context free languages
(Chapter 7 of your textbook, pages 198-236).
-
March 1, 1999.
Today's lecture topic will be continued discussion
of pushdown automata.
-
March 3, 1999.
Today's lecture topic will be continued discussion
of pushdown automata and context-free languages.
-
Homework due.
Assignment 4
will be due on Wednesday, March 3, in class.
-
March 8, 1999.
Today's lecture topic will be continued discussion
of pushdown automata and context-free languages, with
applications to parsing.
-
March 10, 1999.
Today's lecture topic will be continued discussion
of pushdown automata and context-free languages, with
continuation of the discussion of applications to
parsing.
-
March 15, 1999.
Today's lecture will cover the Pumping Lemma for context-free
languages. Please read Chapter 8 of your textbook, pages 237-254.
-
Homework due.
Assignment 5
will be due on Monday, March 15, in class.
A shift-reduce parser in
postscript also in
html
I apologize for the fact that the html file is not currently organized
properly. However, all the relevant information is there: just click
on the links marked "Exercise" to get all the information.
Warning: there is at least one error in this file. Email notification
of errors you detect are strongly encouraged.
-
March 17, 1999.
Today's lecture will cover remaining topics in your textbook,
up through and including Chapter 8, in preparation for the examination
on Monday.
-
Examination. We will have a examination on March 22.
The exam will cover material up to, and including, Chapter 8 in your textbook.
-
March 24, 1999.
Today we will begin the discussion of Turing machines. Please start by
reading the first five sections of Chapter 9 of your textbook, pages
255-276.
-
April 5, 1999.
Today, we continue our discussion of Turing machines. We will explain the
Church-Turing Thesis, and its relevance to the problem of decidability.
Read Chapter 9 of your textbook, pages 255-293.
-
April 7, 1999.
We consider recursive and recursively enumerable
languages. We show that a language is recursive if and only if
it is decidable. We show that the universal language is not recursive,
which is equivalant to saying that the halting problem (the problem of
whether a given machine halts with a given input) is undecidable.
Read Chapter 10 of your textbook, pages 294-310.
-
Homework due.
Assignment 6
will be due on Monday, April 19, in class.
-
April 19, 1999.
Today we will introduce the concept of a general grammar,
also known as a phase-structure grammar or an
unrestricted grammar. The main theorem is that the class
of languages generated by these grammars is precisely the class
of recursively enumerable languages, that is, those that are
accepted by Turing Machines. There are other well-known classes
of grammars which are historically significant, such as
context-sensitive grammars, regular grammars,
and linear grammars.
Today, we will discuss reduction. You have used that word
many times, casually, such as in the sentence, "I can solve the
reachability problem by reducing it to breadth-first search."
Clearly, a precise definition is needed, and we will, together,
invent one!
-
Homework due.
Assignment 7
will be due on Monday, April 26, in class.
-
April 26, 1999. In today's lecture, we will
finally discuss the most amazing fact of all, namely that there
exist undecidable problems, and in fact, problems that are very
easily stated that are undecidable! (For an example, look at
a very quick proof that the Pascal
program halting problem is undecidable.
-
April 28, 1999. In today's lecture, we will
-
May 3, 1999.
Dr. Kazem Taghva will give today's lecture. He will discuss
recursive function theory.
Be sure to read Chapter 13 of the textbook, pages 363-394.
-
May 5, 1999. In today's lecture, we discuss
complexity theory. In particular, we shall define the concept
of NP-completeness.
-
Homework.
Work Assignment 8 by May 12,
but do not turn it in.
-
Final Examination. Our final examination is scheduled
for 6:00 PM on Wednesday, May 12. The examination will be comprehensive.