CS345 Automata Theory and Formal Languages
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.
- 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