Computer Science 456/656
Automata and Formal Languages
Spring 2013

Syllabus

Section numbers refer to Sipser, third edition

1. Deep questions.
   1. Can you "know" pi?
   2. Can anything be bigger than infinity?
   3. Can all truth be discovered by reason?
2. Alphabets, strings, and languages (page 13)
3. Regular languages and finite automata.
   1. Finite automata (1.1, 1.2).
   2. Regular languages and regular expressions (1.3).
   3. The pumping lemma (1.4).
4. Context-free languages
   1. The other pumping lemma (2.3).
5. Context-free grammars (2.1).
   1. Context-free grammars for algebraic languages.
   2. LALR parsing.
   3. Push-down automata (2.2).
   4. Respecting the semantics.
6. Computability and Decidability.
   1. Turing machines (3.1, 3.2, 3.3).
   2. The halting problem and other undecidable problems (4.1, 4.2).
7. Complexity theory.
   1. The polynomial class P-TIME (7.2).
   2. NP-completeness (7.4).
   3. Parallel computation and Nick Pippenger's class (10.5).