[8/21] We finished going over proofs, and began
Chapter 1 of Sipser, on finite state computation. We
went through the fundamental ideas of computation, and
the concept of a finite state machine. A finite state
machine reads a string over a given alphabet, and produces
a yes or no answer. It uses a finite amount of memory,
regardless of the size of the input.
[8/23] We formally defined finite state machines
and began to look at their properties. You should continue
reading Chapter 1 of Sipser. I gave
homework assignment 1,
due 8/25.
[8/25] We went over a solution to the homework, did another
example of finite state machine design, and began to look at
regular operations.
[8/28] We looked more at regular operations, and defined
regular expressions. Homework exercise 2
is due Friday 9/1.
[8/30] We began to study the tools needed to show that
regular expressions and finite state machines have equivalent
descriptive power. The fundamental concept is nondeterminism.
Nondeterministic finite automata (NFAs) are discussed in the text.
[9/1] We demonstrated conversions between different ways
of describing languages. The conversions are as follows.
Regular languages --> NFA(epsilon) <--> NFA <--> DFA
The only remaining conversion is to show how to convert an NFA(epsilon)
to a regular expression. Homework exercise 3
is due Wednesday, 9/6.
[9/6] We spend most of the lecture going over exercises and
doing review of principles of finite state machines and
regular expressions.
[9/8] We showed how to convert an NFAepsilon to an
equivalent regular expression, and look at closure results
(such as the result that, if L is regular then LR is also
regular). Homework exercise 4, due 9/11, was
assigned.
[9/11] We reviewed exercises and material on regular languages.
[9/13] Quiz. We looked at a method for proving that a language
is not regular.
[9/15] We did more examples of proving that a language is
not regular. Exercise 5 was assigned.
[9/18] We began chapter 2 in the text, on context-free
languages.
[9/20] We looked more at context-free grammars, and proved
that any regular expression can be converted into an equivalent
context-free grammar.
[9/22] We looked at push-down machines, and did part of
the proof of the theorem that nondeterministic push-down machines
can recognize all context free languages, and only context-free
languages.
[9/25] We looked more at context-free grammars and push-down
machines. We showed that a language is context-free by designing
a push-down machine for it.
[9/27] We turned to general computation, and began to
accumulate evidence for the Church/Turing Thesis. We are beginning
Chapter 3 of Sipser.
[9/29] We looked more at the Church/Turing Thesis and
the notion of computability.
[10/2] Quiz 2. We looked at some computable problems involving
finite automata.
[10/4] We asked how a problem might be shown
to be uncomputable. We used diagonalization to show that
the halting problem is undecidable.
[10/6] We looked more at diagonalization, and showed that
the language K = {p | p eventually halts on input p} is undecidable.
We also began to look at reductions between problems, and showed
that K reduces to the halting problem.
[10/9] We continued to look at reductions between problems.
[10/13] We did more examples of reductions.
[10/16] We proved Rice's theorem: Every nontrivial transparent
set of programs is undecidable. A set S of programs is transparent if,
whenever two programs p and q are equivalent, either p and q are both
in S or both not in S.
[10/18] We defined and study the Turing recognizable
languages. They are also called the recursively enumerable languages.
[10/20] We defined the m-complete languages and showed that
that halting problem is m-complete.
[10/25] We discussed Post's correspondence problem, and
showed that it is Turing-recognizable.
[10/27] Quiz. We continued looking at Post's
correspondence problem after the quiz.
[10/30] We finished looking at computability.
[11/1] We began the study of complexity theory, where
the cost of performing a computation is taken into account.
[11/3] We went over exercises and
looked at polynomial time computation, and saw a poor
algorithm for computing greatest common divisors.
[11/6] We showed that the problem of computing
greatest common divisors is solvable in polynomial time, and
will ask how a problem might be shown not to be solvable in
polynomial time.
[11/8] We defined nondeterministic polynomial time
computation, and the class NP of decision problems that are
solvable nondeterministically in polynomial time. We define
polynomial time reductions and the notion of NP-completeness,
and looked at a few properties of polynomial time reductions.
[11/10] We went through a sketch of a proof of the
Cook/Levin theorem, that the satisfiability problem is
NP-complet.
[11/13] We showed that 3-SAT is NP-complete and
began looking at the clique problem.
[11/15] We answered questions about homework and showed
how to reduce the 3-SAT problem to the clique problem, thus completing
the proof that the clique problem is NP-complete.
[11/17] Quiz. We will also see another NP-complete problem.