Richard Beigel, Wachman 304, (215)635-3395,
beigel@joda.cis.temple.edu, http://www.cis.temple.edu/~beigel/. Office
hours: TBA. I will be happy to schedule appointments
at other times, and I love to answer questions by email. I try to
read my email every day but Saturday and every evening but Friday.
Textbook
The Language of Machines by Floyd and Beigel.
Supplementary textbooks
If you want a different perspective
on automata theory, see
Highly RecommendedElements of the Theory of Computation
by Lewis and Papadimitriou
Introduction to Automata Theory, Languages, and Computation
by Hopcroft and Ullman
Keeping in touch
Check the class web
page regularly for announcements. I will post helpful hints,
errata, and announcements there. Most handouts and assignments will
be available there as well.
Prerequisite
CIS 540. This is a graduate class in discrete
math. Engineering math will not suffice.
Automata theory is a very formal and mathematical subject. If
you had a hard time in 540, you can expect to have a harder time in
573. It would be a good idea to review discrete mathematics in Chapter 0
of your textbook. Relations, induction, trees, graphs, and number
representations are particularly important. If you have trouble with
proofs, click here.
Synopsis of Course
The course covers computability in
various machine models, and the connection between computability and
formal grammars. Topics include finite automata and regular
languages, push-down automata and context-free languages, Turing
machines and rewriting systems, and undecidability. We will also
cover NP-completeness and an introduction to complexity theory.
Grades
Reading
will be assigned weekly.
On-line assignments
will be assigned occasionally. You must
work alone on them. You will be instructed as to what to hand in.
Problem sets
will be assigned every Wednesday morning.
Do the problem sets in groups of three and turn in a single writeup for
the whole group.
Quizzes
will be given weekly. They will cover the reading,
the lectures, and the homework, so don't let the rest of your group
carry you and don't get behind. Of course, you will have to work
alone on quizzes and exams.
If you miss a quiz for any reason, you get a 0 for that quiz. The two
lowest quiz grades will be dropped.
Informal introduction to machines and programs.
Finite machines, input, output, stacks, counters, Turing
machines, RAMS. Determinism and nondeterminism. Read about
strings and number representations in chapter 0. Review
induction if necessary.
Topic 2
Formal definitions of machines, devices, programs,
and computations. Be sure to read about relations in Chapter 0.
Topic 3
Simulation and Standardization. How can a program
for one type of machine be rewritten for another type of machine?
Standard forms for programs. Minimum and maximum repertories.
Topic 4
Finite machines and regular languages. Kleene's
theorem. Equivalence of DFAs, NFAs, and regular expressions.
Closure properties. Finite transductions. State minimization
and the Myhill-Nerode theorem. Pumping lemma.
Topic 6
Context-free languages. Parse trees, derivations,
and ambiguity. Normal forms. Equivalence with nondeterministic
stack languages. Closure properties. Parsing. Pumping
theorems.
Topic 5
Stack machines. Closure properties for the class of
nondeterministic stack languages. DCFLs.
Topic 7
Computability. Turing machines. Recursive and
r.e. sets. Undecidability of halting problem. Reductions.
Undecidability of first-order logic. Applications to problems in
formal language theory. Hilbert's tenth problem.
Topic 8
Recursion theory.
Topic 9
NP-completeness and an introduction to complexity theory.
Symbol systems, Boolean formula
satisfiability. Polynomial-time bounded reductions. Hamiltonian
path.