Course Description: Introduction to theory of computation through the study of different types of finite state machines.
Prerequisite: MAT 281 or equivalent with a grade of "C" or better.
Time & Place: M W 19:00--20:15 (SBS F101)
Textbook: Automata and Computability (Undergraduate Texts in Computer Science) by Dexter C. Kozen. Spring-Verlag (Publisher), ISBN-10: 0387949070, ISBN-13: 978-0387949079.
Assignment: Exercises will be assigned and collected on a regular basis They are an integral part of the course.
Notes: Here are the notes.
Online Resources: Here are some useful links:
Schedule
| 08-31 | 3 Finite Automata and Regular Sets HW 1 | 09-02 | 4 More on Regular Sets |
|---|---|---|---|
| 09-07 | Labor Day | 09-09 | 5 Nondeterministic Finite Automata |
| 09-14 | 6 Subset Construction | 09-16 | 7,8 Pattern Matching and Regular Expression |
| 09-21 | 9 Regular Expression and Finite Automata | 09-23 | review |
| 09-28 | Test 1 | 09-30 | 10 Homomorphisms |
| 10-05 | 11 Limitations of Finite Automata | 10-07 | 12 Using the Pumping Lemma |
| 10-12 | 19 CFGs and CFLs | 10-14 | 20 Balanced Parentheses |
| 10-19 | 21 Normal Forms | 10-21 | 22 Pumping Lemma for CFLs |
| 10-26 | 23 Pushdown Automata | 10-28 | 24 PDAs and CFGs |
| 11-02 | 25 Simulating NPADs by CFGs | 11-04 | review |
| 11-09 | Test 2 | 11-11 | 28,29 Turing Machines |
| 11-16 | 28,29 Turing Machines | 11-18 | 31 Universal Machines and Diagonalization |
| 11-23 | Thanksgiving | 11-25 | Thanksgiving |
| 11-30 | 31 Universal Machines and Diagonalization | 12-02 | 32 Decidable and Undeciable Problems |
| 12-07 | 33 Reduction | 12-09 | 34 Rice Theorem |
Final Exam 12-14 19:00--21:00 (SBS D215)
Grading Scheme and course requirements
Assignment (20%) 2 Tests (20% Each) Final
(40%)
| A | A- | B+ | B | B- |
| 100-93 | 92-89 | 88-84 | 83-79 | 78-74 |
| C+ | C | C- | D | F |
| 73-69 | 68-64 | 63-59 | 58-50 | < 50 |
Expected outcomes Please refer to the departmental syllabus.
Policies For policies on academic integrity, accommodation for students with disabilities, due dates and make-up work and various other topics, please consult this page .