Table of Contents |
Slides per Page |
| Introduction |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Finite Automata |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Non-deterministic Finite Automata |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Regular Expressions |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Non-Regular Languages |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Context-Free Grammars |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Pushdown Automata |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Non-Context-Free Languages |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Turing Machines |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Variants of Turing Machine |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| The Definition of Algorithm |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Decidable Languages |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| The Halting Problem |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Reducibility |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Time Complexity |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| Complexity Classes P and NP |
1(ps) 1(pdf),
2(ps) 2(pdf) |
| NP-completeness (introduction) |
1(ps) 1(pdf),
2(ps) 2(pdf) |
MINESWEEPER
Introduction to Theory of Automata, Formal Languages, Computation
- CS 4/56201:
|
|
Textbook: "Introduction to the Theory of
Computation." (PWS Publishing, Boston 1997.) (order
on-line)
by Michael Sipser 
HOMEWORKS
-
Problems 0.1 (p. 25); 0.3, 0.7, 0.8 (p. 26); 0.9, 0.10, 0.11 (p. 27). (Due
01/29/2004)
results (pdf)
-
Problems 1.1, 1.2 (p. 83); 1.3, 1.4, 1.5(a-d), 1.6, 1.7(a) (p. 84); 1.8(b,c),
1.12(b) (p. 85). (Due 02/12/2004) results (pdf)
-
Problems
(Due 02/26/2004)
results (pdf)
-
Problems
(Due 03/9/2004)
results (pdf)
-
Problems
(Due 04/6/2004) results (pdf)
-
Problems 3.9 (p.148); 3.13 and 3.15 (p.149). (Due 04/20/2004)
-
Problems:
Do 4.1 (p.168-169) for the DFA from Example 1.3 on p.38.
Do 4.4, 4.7, 4.9 (p.169). (Due 04/29/2004)
EXAMS
-
Thursday, March 30, 2004, 3:15 - 4:30 pm
{Sections 1.1-2.3} Results&Solutions(pdf)
-
Friday, May 7, 2004, 7:45 -10:00 am
{Sections 3.1-4.2; 5.1(pp. 171-176);
7.1-7.3}. FinalInfo(pdf)
|