CS475: Automata, Formal Languages, and Computational Complexity
Fall 2005   Prof. Mahesh Viswanathan

Credits

The lecture notes are based on transparencies of Lenny Pitt and original notes of Mahesh Viswanathan.

The schedule of lectures corresponds to a previous semester (fall 2002), the actual order may change slightly this semester. You might also want to look at Pitt's transparencies for alternate presentations of the material.

Finally, videos of last year's lectures (taught by Professor Pitt) can be viewed here. You must enter your netid as UIUC\mynetid (as in this example), and use your UIUC Active Directory.

Lecture Date Subject Notes
1 8/25 Administrivia, overview, cardinals [PS , PDF , B/W PS, B/W PDF ]
2 8/30 Determinitistic Finite Automata (DFA) [PS , PDF , B/W PS, B/W PDF ]
3 9/1 Nondeterministic Finite Automata (NFA) [PS , PDF , B/W PS, B/W PDF ]
4 9/6 Regular Expressions [PS , PDF , B/W PS, B/W PDF ]
5 9/8 Regular Expressions and Regular languages [PS , PDF , B/W PS, B/W PDF ]
6 9/13 Expressiveness and pumping lemma [PS , PDF , B/W PS, B/W PDF ]
7 9/15 Closure Properties [PS , PDF , B/W PS, B/W PDF ]
8 9/20 Decision Problems and Myhill Nerode Theorem [PS , PDF , B/W PS, B/W PDF ]
9 9/22 DFA Minimization [PS , PDF , B/W PS, B/W PDF ]
10 9/27 Context Free Grammars [PS , PDF , B/W PS, B/W PDF ]
11 9/29 Pushdown Automata [PS , PDF , B/W PS, B/W PDF ]
-- 10/4 Midterm 1 [PS , PDF ]
12 10/6 Context Free Grammars and Pushdown Automata [PS , PDF , B/W PS, B/W PDF ]
13 10/11 CFGs and PDAs (contd) [PS , PDF , B/W PS, B/W PDF ]
14 10/13 Deterministic Pushdown Automata and Simplifying Grammars [PS , PDF , B/W PS, B/W PDF ]
15 10/18 Normal Forms and Pumping Lemma [PS , PDF , B/W PS, B/W PDF ]
16 10/20 Closure properties of CFLs [PS , PDF , B/W PS, B/W PDF ]
17 10/25 CYK Algorithm and Chomsky Hierarchy [PS , PDF , B/W PS, B/W PDF ]
18 10/27 Turing Machines [PS , PDF , B/W PS, B/W PDF ]
-- 11/1 Midterm 2 [PS , PDF ]
19 11/3 Turing Machines and their Variants [PS , PDF , B/W PS, B/W PDF ]
20 11/8 Church Turing Thesis and Additional Models of Computation [PS , PDF , B/W PS, B/W PDF ]
21 11/10 Closure Properties and Undecidability [PS , PDF , B/W PS, B/W PDF ]
22 11/15 Many-one Reductions, Hardness and Rice's Theorem [PS , PDF , B/W PS, B/W PDF ]
23 11/17 Measuring Complexity, Speedup/compression Theorems, Hierarchy Theorems [PS , PDF , B/W PS, B/W PDF ]
24 11/29 Palindromes (Space-Time Tradeoff), Communication Complexity [PS , PDF , B/W PS, B/W PDF ]
25 12/1 Nondeterministic Complexity Classes, Reductions, Hardness, Completeness Revisited [PS , PDF , B/W PS, B/W PDF ]
26 12/6 Cook-Levin Theorem, and Self-Reducibility [PS , PDF , B/W PS, B/W PDF ]
27 12/8 Complementation and Concluding Remarks [PS , PDF , B/W PS, B/W PDF ]


Acknowledgement: These lecture notes are very close in spirit to those of professor Leonard Pitt . They have also been influenced by courses taught by professor Steven Rudich .


Acknowledgement: These lecture notes are very close in spirit to those of professor Leonard Pitt . They have also been influenced by courses taught by professor Steven Rudich .