CS 345/541 Automata Theory and Formal Languages
Fall 2006

Official Course Description. This course gives an introduction to formal languages and their relation to automata. Topics include deterministic and non-deterministic finite automata, regular expressions and languages, closure properties and decision procedures for context-free languages, recursive and recursively enumerable sets, Turing machines, and decidability. Some aspects of computational complexity may also be explored.

Prerequisites. CS142, and MA211 or MA346.

Location and Times. Science Center 303, TuTh 2:30-3:45.

Instructor. Alexis Maciel. Science Center 379, 268-2385, alexis@clarkson.edu.

Office Hours. M 2:30-4:30, W 9:30-11:30, Th 9:30-10:30.

Required Text. Michael Sipser, Introduction to the Theory of Computation, 2nd edition, Thomson Course Technology, 2006. ISBN 0-534-95097-3.

Course Objectives.

  1. To teach you concepts and results that constitute the foundations of computing, that is, the knowledge that allows us to understand what computation is. These include the Turing machine, the existence of undecidable problems, and the P versus NP question.

  2. To teach you concepts and results of practical importance such as those related to regular expressions, context-free grammars, undecidability and NP-completeness.

  3. To increase your ability to think and communicate clearly.
Demonstrable outcomes. By the end of the semester,
  1. You will have a good understanding of concepts and results from the theory of computation, covering the range of topics listed below.

  2. You will be able to solve problems related to those topics.

Topics to be covered. Deterministic and nondeterministic finite automata, regular expressions, regular languages, the Pumping Lemma, context-free grammars, pushdown automata, context-free languages, deterministic and nondeterministic Turing machines, the Church-Turing thesis, and undecidable problems (essentially, most of Chapters 1 to 5). Time permitting, some notions of computational complexity, such as time and space complexity, the classes P and NP, and NP-completeness (Chapter 7).

Grading. Your evaluation will be based on several homework assignments, two tests, two self-assessments of your performance on the tests, one for each test, and a final exam. Your course grade will be computed using the following formula:

25% A + 20% T1 + 5% SA1 + 20% T2 + 5% SA2 + 25% F

At the final exam, you will have the option of writing a make-up exam that can replace half of each of the two tests. The minimum grade you can get on a self-assessment is the grade you got on the corresponding test. Tentative dates for the tests are Wednesday, October 18 and Wednesday, November 15. These will be evening exams. All students are required to write the final exam (no exemptions).

Policy for missed work. There will be no make-up assignments. Late assignments may be accepted if a good excuse is provided and if arrangements are made at a reasonable time, in advance, if possible. Make-up tests can be arranged under the same conditions. Other special arrangements can be made for students forced to miss more than a few days of class.