### CS345 Automata Theory and Formal Languages
Fall 1999
**Instructor**: Christino Tamon **Lectures**: MWF 1-2pm SC356
**Office hours**: MW 2-3pm, 4-5pm and F 2-3pm SC373 **Capacity:
50** **Text**: Michael Sipser. *Introduction to the Theory of
Computation*. PWS Publishing Company, 1997. **Grading scheme**:
- Final exam: 40%
- Midterm exam: 20%
- Assignments and quizzes: 40%
**Course Plan**: In this course we will focus on the question: *What
kind of problems are solvable by the computer?* To do this we will define
a mathematically precise formulations of *problems*, *solvable*,
and *computer*. We will study abstract formulations of a computer as
different types of automata: finite automata, pushdown automata and Turing
machines. In a parallel fashion, we will develop notions of problems as
different types of languages: regular, context-free, and recursive languages.
We then show that there is a tight correspondence between these automata
and language characterizations. The course will also cover closure properties,
hardness (Pumping Lemmas), and other relevant topics. Important connections
to compiler theory will be emphasized throughout the course.
**Schedule**
- Part 1: Mathematical notations and proof techniques (review of MA211).
- Part 2: DFAs. Regular languages.
- Part 3: NFAs. Equivalence between DFAs and NFAs. Closures.
- Part 4: Regular expressions. Equivalence between RE and NFAs.
- Part 5: NonRegular languages and the Pumping Lemmas.
- Part 6: Context-free languages and Pushdown Automata (PDA).
- Part 7: Context-free grammars. Equivalence with PDAs.
- Part 8: Non-context-free languages and the Pumping Lemmas.
- Part 9: Unrestricted grammars (or simply Grammars)
- Part 10: Turing Machines.
- Part 11: Equivalence of Turing Machines and Grammars.
- Part 12: Variants of TMs. Halting problem.
**Assignments**: coming soon. |