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
- E-mail: 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:30-11:30,3-4, W 2-3, 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) 4-5 pm
times: (Section 2) 7-8 pm
- Jonathan David Hay, DC2126, x6462, jd2hay@neumann,
Office Hours (for Assignment #4)
Tuesday - Friday, November 16-19 3:00-4:00pm.
Monday - Tuesday, November 22-23 3:00-4: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, 2-5,
Tuesday Oct 26, 1:30-3:30,
Thursday Oct 28, 2-4,
Tuesday Nov 2, 2-5,
Thursday Nov 11, 3-6.
Tutorial for Assignments 2 and 3: EL204, from 5-7 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 eps-transition.
- Closure properties of regular languages.
- Equivalence of DFA and Regular expression. (Kleene Theorem).
- Non-regularity 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
- Church-Turing 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 eps-transition.
- Closure properties of regular languages.
- Equivalence of DFA and Regular expression. (Kleene Theorem).
- Non-regularity 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, McGraw-Hill, 1997. I reserved one
copy of this book in the David Center Library.