Created: Wed 14 Jan 2004
Last modified:
Note: This is an approximate syllabus; it may change at any time.
- Lecture 01, Wed 01-07-04
- Introduction; admistrivia; overview of CSG714
- DFAs, state diagrams and examples
- Formal definitions; regular languages; regular operations;
regular expressions
- Reading: Sipser 0, 1.1
- Lecture 02, Wed 01-14-04
- Closure properties; non-determinism; equivalence of NFAs and DFAs
- Regular expressions; equivalence of RE and FA
- Reading: Sipser 1.2-1.3
- Homework 01 assigned
- Lecture 03, Wed 01-21-04
- Finish equivalence of RE and FA
- Non-regular languages and the Pumping Lemma
- Closure properties
- Minimization of FA
- Reading: Sipser 1.4
- Homework 01 due
- Homework 02 assigned
- Lecture 04, Wed 01-28-04
- Context-free languages; context-free grammars; ambiguity
- Compare RLs and CFLs
- Pushdown automata
- Reading: Sipser 2.1-2.2
- Homework 02 due
- Homework 03 assigned
- Lecture 05, Wed 02-04-04
- Equivalence of CFLs and PDAs
- Pumping Lemma for CFLs
- Closure properties
- Reading: Sipser 2.2-2.3
- Homework 03 due
- Homework 04 assigned
- Lecture 06, Wed 02-11-04
- Turing Machines; state diagrams and examples; Church-Turing thesis
- Formal definitions; decidable and recognizable languages
- Reading: Sipser 3.1, 3.3
- Homework 04 due
- Homework 05 assigned
- Lecture 07, Wed 02-18-04
- Turing Machine variants: multi-tape and non-determinisitic
- Decidability; cardinality of infinite sets; diagonalization
- Reading: Sipser 3.2, 4.1-4.2
- Homework 05 due
- Midterm exam assigned
- Lecture 08, Wed 02-25-04
- Halting Problem
- Reducibility
- Reading: Sipser 4.2, 5.1
- Midterm exam due
- Lecture 09, Wed 03-10-04
- Rice's Theorem
- PCP
- Reading: Sipser 5.2
- Homework 06 assigned
- Lecture 10, Wed 03-17-04
- Lecture 11, Wed 03-24-04
- Lecture 12, Wed 03-31-04 (Note: Class meets in 149CN)
- Lecture 13, Wed 04-07-04
- Lecture 14, Wed 04-14-04
- Advanced topics, TBA
- Homework 10 due
- Final exam assigned
- Wed 04-21-04
Switch to:
jaa@ccs.neu.edu