COMP 301 - Automata Theory |
Fall 2002 |
| Instructor-- | Danny Krizanc |
| Office-- | 631 Science Center |
| Office Hours-- | Wednesdays 2:00-4:00 or by appointment |
| Phone-- | 860-685-2186 |
| E-mail-- | dkrizanc at wesleyan.edu |
This course in an introduction to formalisms studied in computer science and mathematical models of computing devices. Topics to be discussed include regular, context-free, and decidable languages and their correspondence to finite-state automata, push-down automata and Turing machines. Topics in complexity theory will be covered given sufficient time.
The following (in my opinion pretty good) textbook is required:
There is a long list of competitors, among the better of which are:
There will be eight small written assignments worth a total of sixty per cent of the grade. There will be two in-class tests worth twenty per cent each.
The following is an ambitious plan of the course and is subject to change.
|
|
Topic | Readings |
|
|
Finite Automata | Chapter 1.1-2 |
|
|
Regular Languages | Chapter 1.3-4 |
|
|
Pushdown Automata and Context-free Grammars | Chapter 2 |
|
|
|
Chapters 1-2 |
|
|
Turing Machines | Chapter 3 |
|
|
Decidability | Chapter 4.1 |
|
|
The Halting Problem | Chapter 4.2 |
|
|
Reducibility | Chapter 5 |
|
|
Complexity Theory | Chapter 7 |
|
|
|
Chapters 3-5,7 |
| Report problems to dkrizanc at wesleyan.edu
|