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. Snell 169, MWF 1:00-1:50.

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

Office Hours. MW 2:00-3:30, TuTh 2:30-3: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.

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 (A), two tests (T) and a final exam (F). Your course grade will be computed using the following formula:

The final exam will not be cumulative. At the final exam, you will have the option of writing make-up exams for Tests 1 and 2. Tentative dates for the tests are Thursday, October 15 and Thursday, November 12. 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.

Laptops and other electronic devices. These are permitted in class only for the purpose of taking notes. Nothing else. Please turn off your phone ringers while in class.