CS345 Automata Theory and Formal Languages
Fall 1998

Instructor: Christino Tamon
Lectures: MWF 1-2pm SC344
Office hours: MW 2-4pm and F 2-3pm or by appointment SC373

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.
Back to Christino Tamon's home page.