Fall 2007

**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.** M 2:00-3:00, Tu 2:30-3:30, W 10:00-11:00 (in SC 334), W
2:00-3:00, Th 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.**

- 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.
- To teach you concepts and results of practical importance such as those related to regular expressions, context-free grammars, undecidability and NP-completeness.
- To increase your ability to think and communicate clearly.

- You will have a good understanding of concepts and results from the theory of computation, covering the range of topics listed below.
- 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), two test corrections (C), one for each test, 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 18 and Thursday, 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.

**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.