CS273: Automata, Formal Languages, and Computational Complexity
Spring 2006 Profs. Pitt and Fleck
CS273: Automata, Formal Languages, and Computational Complexity
Spring 2006 Profs. Pitt and Fleck
This is a preliminary outline of the contents of each lecture. As the term progresses, we will correct it and add links to the slides from lecture. The pdf or txt link under the column "Slides" are the screen-capture of what was done (in real time) in Tuesday large lecture, or are typed notes from Thursday section. A link [V.n] is to prepared slides very closely covering the same material, from fall 2005. (The link tells you to see lecture numbered n.)
| Week | Date | Lecture | Material covered | Slides | Readings |
|---|---|---|---|---|---|
| 1 | 1/17 | 1 | Administrivia, overview, cardinals | pdf
[V.1] |
|
| 1/19 | 2 | Strings, Languages, induction on strings | Ch. 1, Sec. 2.2, Box on p. 310 | ||
| 2 | 1/24 | 3 | DFAs (with and without output) | pdf
[V.2] |
|
| 1/26 | 4 | More examples of DFAs, more proofs about DFAs | txt | ||
| 3 | 1/31 | 5 | NFA and nondeterminism, equivalence of NFAs and DFAs, NFAs with epsilon-transitions. | pdf
[V.3] |
Sections 2.3, 2.4, 2.5 |
| 2/2 | 6 | Regular expressions, equivalence with DFAs and NFAs | |||
| 4 | 2/7 | 7 | Equivalence of DFA's and regular expressions, closure properties of regular languages | ||
| 2/9 | 8 | Finish equivalence of DFA's and regular expressions, more examples | |||
| 5 | 2/14 | 9 | Pumping Lemma, proofs of non-regularity | ||
| 2/16 | 10 | More examples of pumping lemma | txt | ||
| 6 | 2/21 | 11 | DFA state minimization | ||
| 2/23 | 12 | DFA decision problems | txt | ||
| 7 | 2/28 | review for first midterm | |||
| 3/2 | 13 | Context free grammars | txt | ||
| 8 | 3/7 | 14 | Intro to PDAs | ||
| 3/9 | 15 | More on PDAs, equiv w/ grammars | [ pdf, latex ] | ||
| 9 | 3/14 | 16 | deterministic PDAs, normal forms for CF grammars | ||
| 3/16 | 17 | more normal forms, pumping lemma for CFLs | |||
| break | 3/21 | vegetating in the sun | |||
| 3/23 | hiking, swimming | ||||
| 10 | 3/28 | 18 | left recursion removal, CFL closure properties | ||
| 3/30 | 19 | visibly pushdown automata, decision problems, CYK algorithm | VPAs CYK | ||
| 11 | 4/4 | review for second midterm | 4/6 | 20 | Intro TMs, IDs |
| 12 | 4/11 | 21 | Programming tricks for TM's, subroutine calls, multiple tracks, multiple dimensions | ||
| 4/13 | 22 | Multi-tape and nondeterministic TMs | |||
| 13 | 4/18 | 23 | simulation of RAMs by TMs, TM's as generators | ||
| 4/20 | 24 | relating generation to acceptance, closure properties | pdf-1 pdf-2 | ||
| 14 | 4/25 | 25 | Universal TM undecidability | pdf-1 html-2 | |
| 4/27 | 26 | Proving undecidability via reductions | pdf-1 html2 | ||
| 15 | 5/2 | More examples of undecidability, course evals |
This is the first time this version of the course has been taught, but much of the material was previously covered in CS 475. Therefore, we are providing materials from that course. You may also wish to consult Prof. Viswanathan's slides from fall 2005 or Prof. Pitt's slides from fall 2003. Videos of Prof. Pitt's lectures from last year can be viewed here. You must enter your netid as UIUC\mynetid (as in this example), and use your UIUC Active Directory password.
