CS360 Home Page
Theory of Computation
Fall, 1999, Ming Li
Class on Wed. Oct. 20 is cancelled.
Contents

Ming Li
 Office: DC 2339
 Phone: x4659
 Email: mli@math
 Office Hours: Wednesday & Friday, 10:30  12:00 AM.
You are welcome to come by any other time. I will be happy to help
if I am not busy.
 Bruce Fraser, DC2525, x3469, cbfraser@neumann,
Office Hours:. T 10:3011:30,34, W 23, On the weeks of the 27th
(Sept), 4th,11th (oct), for assignment 1.
Tutorial: place: EL 204 (Engineering Lecture Hall)
date: Oct 4,1999
times: (Section 1) 45 pm
times: (Section 2) 78 pm
 Jonathan David Hay, DC2126, x6462, jd2hay@neumann,
Office Hours (for Assignment #4)
Tuesday  Friday, November 1619 3:004:00pm.
Monday  Tuesday, November 2223 3:004:00pm.
First Tuesday, Wednessday and Thursday after assignments (#4) handed back.
Office Hours before Midterm Exam: Tuesday, October 26 3:00  4:00pm/
 John Loftus, DC2129, x2333, ja3loftus@neumann,
Office Hours (for Assignments #2,3): Thursday Oct 14, 25,
Tuesday Oct 26, 1:303:30,
Thursday Oct 28, 24,
Tuesday Nov 2, 25,
Thursday Nov 11, 36.
Tutorial for Assignments 2 and 3: EL204, from 57 p.m.
Section 1, Tuesday Oct 19,
Section 2, Wed. Oct 20,
Section 1, Wed. Nov 3,
Section 2, Thursday Nov 4.
 Regular Expressions and the regular languages they define.
 DFA, NFA, converting NFA to DFA, removing epstransition.
 Closure properties of regular languages.
 Equivalence of DFA and Regular expression. (Kleene Theorem).
 Nonregularity and the Pumping Lemma. How to use Pumping Lemma.
 Context free grammars (CFG) and context free languages (CFL).
 Regular grammars.
 Pushdown automata.
 Pushdown automata and CFG: equivalence.
 Properties of CFL: closure properties, periodicity properties
(pumping lemma for CFL), algorithmic properties (decision
procedures). Removing useless symbols and epsilon rules.
 Chomsky Normal Form.
 Parsing if there is time.
 DCFL  Deterministic CFL
 Turing Machines, examples.
 Turing acceptable, Turing decidable
 Various types of Turing machines, extensions, equivalence
 Nondeterministic Turing machines
 ChurchTuring thesis
 Recursive functions, r.e. functions
 Encoding Turing machines, Universal Turing machines
 Computability and Decidability, Turing decidability, Turing
acceptability, Turing enumerability, basic theorems.
 Reductions
The following assignments will become readable on the handout
dates.
The midterm exam will cover topics we covered in the class
till Wed. Oct. 27, inclusive. These include
 Regular Expressions and the regular languages they define.
 DFA, NFA, converting NFA to DFA, removing epstransition.
 Closure properties of regular languages.
 Equivalence of DFA and Regular expression. (Kleene Theorem).
 Nonregularity and the Pumping Lemma. How to use Pumping Lemma.
 Context free grammars (CFG) and context free languages (CFL).
 Regular grammars.
 Pushdown automata.
 Pushdown automata and CFG: equivalence.
 Properties of CFL: closure properties, periodicity properties
(pumping lemma for CFL), algorithmic properties (decision
procedures). Removing useless symbols and epsilon rules.
 Chomsky Normal Form.
 Sample Questions (Note, these are not
meant to be inclusive or exhaustive.)
Approximately 30% of the final exam will cover topics we covered before
the midterm exam, and 70% of the final exam will cover
topics we taught after the midterm.
Here are some sample questions
for the final exam. The actual exam will probably contain more
questions than this sample question list  this list is only
meant to provide with you some ideas about the kind
of questions to be expected in the final exam. Remember the tutorials
will be Dec. 18, 5pm, and Dec. 20, 1pm, both in MC 2605. I will be
there to answer all questions.

Everything we have covered in class. See course topics list.
Textbook is "Introduction to Languages and the Theory of Computation"
by John C. Martin, 2nd Edition, McGrawHill, 1997. I reserved one
copy of this book in the David Center Library.