CS 541 Introduction to Automata Theory
and Formal Languages
Fall 1998

Brief Description. This course is divided into three main parts: finite automata, context-free languages and Turing machines. Below are some of the topics that will be studied.

  • Finite automata: deterministic and nondeterministic, regular expressions, Pumping Lemma

  • Context-free languages: context-free grammars, Chomsky Normal Form, pushdown automata, Pumping Lemma

  • Turing machines: deterministic and nondeterministic, variants, undecidability

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

Office Hours. Monday to Friday 10:30-11:30 a.m., and by appointment.

Required Text.

    Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, MA, 1997.
We will cover at least Chapters 1 to 4 and parts of 5.


Homework assignments 30%
Two tests 30%
Final exam 40%

The assignment policy for the course will be stated on the first assignment. Tentative dates for the tests: October 16 and November 18.