CS154 Outline
DateTopicReading
1/5Review of proof techniques, intro. to automata1, 2.1
1/10Deterministic and nondeterministic finite automata2.2--2.4
1/12Epsilon-NFA's, regular expressions2.5, 3.1--3.3
1/19Properties of regular languages 3.4, 4.1, 4.2
1/24Algorithms for regular languages4.3, 4.4
1/26Context-free grammars5.1--5.3
1/31Ambiguous grammars, pushdown automata5.4, 6.1, 6.2
2/2PDA/CFG equivalence, deterministic PDA's6.3, 6.4
2/7MidtermThrough 2/2 lecture
2/9Chomsky-normal-form grammars, pumping lemma7.1, 7.2
2/14Closure properties and algorithms for CFL's7.3, 7.4
2/16Introduction to Turing machines8.1--8.3
2/23Variations of Turing machines8.4, 8.5
2/28Decidability, recursive and RE languages9.1--9.3
3/1Some ``real'' undecidable problems9.4, 9.5
3/6P, NP, and an intractable problem10.1, 10.2
3/8NP-complete problems10.3, 10.4