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.