CS 345/541 Automata Theory and Formal
Languages

Fall 2009

Syllabus

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

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